本文共 15262 字，大约阅读时间需要 50 分钟。

First try

/* 试着写一个最大堆 */#include <iostream>#include <math.h>using namespace std;int swap(int *, int *);int main(){       int array[10];    int height;    for (int i = 0; i < 10; i++)    {           cin >> array[i];    }    for (int height = 1; height < 4; height++)    {           for (int i = 0; i < pow(height); i++)        {               int parent_node = pow(2, height - 1);            int left_node = pow(2, height + i);            int right_node = left_node + 1;            if (array[left_node] < array[right_node])   // 交换左右结点，使左结点大于右结点            {                   swap(&array[left_node], &array[right_node]);            }            if (array[parent_node] < array[left_node])            {                   swap(&array[parent_node], &array[left_node];            }        }    }}int swap(int *num1, int *num2){       int temp = *num1;    *num1 = *num2;    *num2 = temp;    return 0;}

try to shorten the “if” part

/* 试着写一个最大堆 */#include <iostream>#include <math.h>using namespace std;int swap(int *, int *);int main(){       int array[10];    int height;    for (int i = 0; i < 10; i++)    {           cin >> array[i];    }    for (int height = 1; height < 4; height++)    {           for (int i = 0; i < pow(height); i++)        {               int parent_node = pow(2, height - 1);            int left_node = pow(2, height + i);            int right_node = left_node + 1;            array[left_node] < array[right_node] ? swap(&array[left_node], &array[right_node]) : 1;     // 交换左右结点，使左结点大于右结点            array[parent_node] < array[left_node] ? swap(&array[parent_node], &array[left_node]) : 1;        }    }}int swap(int *num1, int *num2){       int temp = *num1;    *num1 = *num2;    *num2 = temp;    return 0;}

Do compare and swap at the same time

a little program to test

#include <iostream>using namespace std;int cas(int *, int *);int main(){       int a, b;    cin >> a >> b;    cas(&a, &b);    cout << "a = " << a << endl;    cout << "b = " << b << endl;    return 0;}int cas(int *num1, int *num2){       if (*num1 < *num2)    {           int temp = *num1;        *num1 = *num2;        *num2 = temp;    }    return 0;}

Great! Subsititude the previous one

/* 试着写一个最大堆 */#include <iostream>#include <math.h>using namespace std;int cas(int *, int *);int main(){       int array[10];    int height;    for (int i = 0; i < 10; i++)    {           cin >> array[i];    }    for (int height = 1; height < 4; height++)    {           for (int i = 0; i < pow(height); i++)        {               int parent_node = pow(2, height - 1);            int left_node = pow(2, height + i);            int right_node = left_node + 1;            cas(&array[left_node], &array[right_node]);     // 交换左右结点，使左结点大于右结点            cas(&array[parent_node], &array[left_node]);        }    }}int cas(int *num1, int *num2){       if (*num1 < *num2)    {           int temp = *num1;        *num1 = *num2;        *num2 = temp;    }    return 0;}

Warning!

Test by a little program

#include <iostream>#include <math.h>using namespace std;int main(){       int a, b;    cin >> a >> b;    cout << (int)pow(a, b);    return 0;}

Modify the previous one

/* 试着写一个最大堆 */#include <iostream>#include <math.h>using namespace std;int cas(int *, int *);int main(){       int array[10];    int height;    for (int i = 0; i < 10; i++)    {           cin >> array[i];    }    for (int height = 1; height < 4; height++)    {           for (int i = 0; i < (int)pow(2, height); i++)        {               int parent_node = (int)pow(2, height - 1);            int left_node = (int)pow(2, height + i);            int right_node = left_node + 1;            cas(&array[left_node], &array[right_node]);     // 交换左右结点，使左结点大于右结点            cas(&array[parent_node], &array[left_node]);        }    }    for (int i = 0; i < 10; i++)    {           cout << array[i];    }}int cas(int *num1, int *num2){       if (*num1 < *num2)    {           int temp = *num1;        *num1 = *num2;        *num2 = temp;    }    return 0;}

Warning! Return negative number

Change some parameter

/* 试着写一个最大堆 */#include <iostream>#include <math.h>using namespace std;int cas(int *, int *);int main(){       int array[10];    int height;    for (int i = 0; i < 10; i++)    {           cin >> array[i];    }    for (int height = 1; height < 4; height++)    {           for (int i = 0; i < (int)pow(2, height - 1); i++)        {               int parent_node = (int)pow(2, height - 1 + i);            int left_node = (int)pow(2, height + i);            int right_node = left_node + 1;            cas(&array[left_node], &array[right_node]);     // 比较并交换左右结点，使左结点大于右结点            cas(&array[parent_node], &array[left_node]);        }    }    for (int i = 0; i < 10; i++)    {           cout << array[i] << endl;    }}int cas(int *num1, int *num2){       if (*num1 < *num2)    {           int temp = *num1;        *num1 = *num2;        *num2 = temp;    }    return 0;}

Input: 1 2 3 4 5 6 7 8 9 0

Output:
1
4
6
3
9
5
7
8
4200496
0

Add one more cas command

/* 试着写一个最大堆 */#include <iostream>#include <math.h>using namespace std;int cas(int *, int *);int main(){       int array[10];    int height;    for (int i = 0; i < 10; i++)    {           cin >> array[i];    }    for (int height = 1; height < 4; height++)    {           for (int i = 0; i < (int)pow(2, height - 1); i++)        {               int parent_node = (int)pow(2, height - 1 + i);            int left_node = (int)pow(2, height + i);            int right_node = left_node + 1;            cas(&array[left_node], &array[right_node]);     // 比较并交换左右结点，使左结点大于右结点            cas(&array[parent_node], &array[left_node]);            cas(&array[left_node], &array[right_node]);        }    }    for (int i = 0; i < 10; i++)    {           cout << array[i] << endl;    }    }int cas(int *num1, int *num2){       if (*num1 < *num2)    {           int temp = *num1;        *num1 = *num2;        *num2 = temp;    }    return 0;}

Input: 1 2 3 4 5 6 7 8 9 0

Output:
1
4
6
2
9
3
7
8
4200528
0

一番修改……

/* 试着写一个最大堆 */#include <iostream>#include <math.h>using namespace std;int cas(int *, int *);int main(){       int array[10];    int height;    for (int i = 0; i < 10; i++)    {           cin >> array[i];    }    for (int height = 1; height < 4; height++)    {           for (int i = 0; i < (int)pow(2, height - 1); i++)        {               int parent_node = (int)pow(2, height - 1 + i) - 1;            int left_node = (int)pow(2, height) + i;            int right_node = left_node + 1;            cas(&array[left_node], &array[right_node]);     // 比较并交换左右结点，使左结点大于右结点            cas(&array[parent_node], &array[left_node]);        }    }    for (int i = 0; i < 10; i++)    {           cout << array[i] << endl;    }    }int cas(int *num1, int *num2){       if (*num1 < *num2)    {           int temp = *num1;        *num1 = *num2;        *num2 = temp;    }    return 0;}

成功地把自己给整懵b了……还是先简化模型，总共7个元素试试

1. 2 跟 3 换

2. 1 跟 3 换

3. 1 跟 2 换

换3次足够

/* 试着写一个最大堆 */#include <iostream>#include <math.h>using namespace std;int cas(int *, int *);int main(){       int array[7];    int height;    for (int i = 0; i < 7; i++)    {           cin >> array[i];    }    for (int i = 0; i < 3; i++)     // 3 为树高    {           // parent_node = i        int left_node = 2 * i + 1;        int right_node = left_node + 1;        cas(&array[left_node], &array[right_node]);     // 比较并交换左右结点，使左结点大于右结点        cas(&array[i], &array[left_node]);        cas(&array[left_node], &array[right_node]);    }    for (int i = 0; i < 7; i++)    {           cout << array[i] << endl;    }    }int cas(int *num1, int *num2){       if (*num1 < *num2)    {           int temp = *num1;        *num1 = *num2;        *num2 = temp;    }    return 0;}

……还是失败了！尝试从后往前排好了！

/* 试着写一个最大堆 */#include <iostream>#include <math.h>using namespace std;int cas(int *, int *);int main(){       int array[7];    int height;    for (int i = 0; i < 7; i++)    {           cin >> array[i];    }    for (int i = 2; i >= 0; i--)     // 3 为树高    {           // parent_node = i        int left_node = 2 * i + 1;        int right_node = left_node + 1;        cas(&array[left_node], &array[right_node]);     // 比较并交换左右结点，使左结点大于右结点        cas(&array[i], &array[left_node]);        cas(&array[left_node], &array[right_node]);    }    for (int i = 0; i < 7; i++)    {           cout << array[i] << endl;    }    }int cas(int *num1, int *num2){       if (*num1 < *num2)    {           int temp = *num1;        *num1 = *num2;        *num2 = temp;    }    return 0;}

貌似好很多了……

放弃思考，直接再来一次for

/* 试着写一个最大堆 */#include <iostream>#include <math.h>using namespace std;int cas(int *, int *);int main(){       int array[7];    int height;    for (int i = 0; i < 7; i++)    {           cin >> array[i];    }    for (int i = 2; i >= 0; i--)     // 3 为树高    {           // parent_node = i        int left_node = 2 * i + 1;        int right_node = left_node + 1;        cas(&array[left_node], &array[right_node]);     // 比较并交换左右结点，使左结点大于右结点        cas(&array[i], &array[left_node]);        cas(&array[left_node], &array[right_node]);    }    for (int i = 2; i >= 0; i--)     // 3 为树高    {           // parent_node = i        int left_node = 2 * i + 1;        int right_node = left_node + 1;        cas(&array[left_node], &array[right_node]);     // 比较并交换左右结点，使左结点大于右结点        cas(&array[i], &array[left_node]);        cas(&array[left_node], &array[right_node]);    }    for (int i = 0; i < 7; i++)    {           cout << array[i] << endl;    }    }int cas(int *num1, int *num2){       if (*num1 < *num2)    {           int temp = *num1;        *num1 = *num2;        *num2 = temp;    }    return 0;}

效果惊人！！

尝试第三层

/* 试着写一个最大堆 */#include <iostream>#include <math.h>using namespace std;int cas(int *, int *);int main(){       int array[15];    int height;    for (int i = 0; i < 15; i++)    {           cin >> array[i];    }    for (int i = 6; i >= 0; i--)     // 3 为树高    {           // parent_node = i        int left_node = 2 * i + 1;        int right_node = left_node + 1;        cas(&array[left_node], &array[right_node]);     // 比较并交换左右结点，使左结点大于右结点        cas(&array[i], &array[left_node]);        cas(&array[left_node], &array[right_node]);    }    for (int i = 6; i >= 0; i--)     // 3 为树高    {           // parent_node = i        int left_node = 2 * i + 1;        int right_node = left_node + 1;        cas(&array[left_node], &array[right_node]);     // 比较并交换左右结点，使左结点大于右结点        cas(&array[i], &array[left_node]);        cas(&array[left_node], &array[right_node]);    }    for (int i = 0; i < 15; i++)    {           cout << array[i] << endl;    }    }int cas(int *num1, int *num2){       if (*num1 < *num2)    {           int temp = *num1;        *num1 = *num2;        *num2 = temp;    }    return 0;}

有点缺陷，是不是大循环的次数跟层数有关呢？

/* 试着写一个最大堆 */#include <iostream>#include <math.h>using namespace std;int cas(int *, int *);int main(){       int array[15];    int height = 4;    for (int i = 0; i < 15; i++)    {           cin >> array[i];    }    for (int i = 0; i < height; i++)    {           for (int j = 6; j >= 0; j--)        {               // parent_node = j            int left_node = 2 * j + 1;            int right_node = left_node + 1;            cas(&array[left_node], &array[right_node]);     // 比较并交换左右结点，使左结点大于右结点            cas(&array[j], &array[left_node]);            cas(&array[left_node], &array[right_node]);        }    }    for (int i = 0; i < 15; i++)    {           cout << array[i] << endl;    }    }int cas(int *num1, int *num2){       if (*num1 < *num2)    {           int temp = *num1;        *num1 = *num2;        *num2 = temp;    }    return 0;}

emmm有点迷，好像不对
改成height成了

/* 试着写一个最大堆 */#include <iostream>#include <math.h>using namespace std;int cas(int *, int *);int main(){       int array[15];    int height = 4;    for (int i = 0; i < 15; i++)    {           cin >> array[i];    }    for (int i = 0; i < height; i++)    {           for (int j = 6; j >= 0; j--)        {               // parent_node = j            int left_node = 2 * j + 1;            int right_node = left_node + 1;            cas(&array[left_node], &array[right_node]);     // 比较并交换左右结点，使左结点大于右结点            cas(&array[j], &array[left_node]);            cas(&array[left_node], &array[right_node]);        }    }    for (int i = 0; i < 15; i++)    {           cout << array[i] << endl;    }    }int cas(int *num1, int *num2){       if (*num1 < *num2)    {           int temp = *num1;        *num1 = *num2;        *num2 = temp;    }    return 0;}

看得眼花……简陋地优化一下输出先

/* 试着写一个最大堆 */#include <iostream>#include <math.h>using namespace std;int cas(int *, int *);int main(){       int array[15];    int height = 4;    for (int i = 0; i < 15; i++)    {           cin >> array[i];    }    for (int i = 0; i < height; i++)    {           for (int j = 6; j >= 0; j--)        {               // parent_node = j            int left_node = 2 * j + 1;            int right_node = left_node + 1;            cas(&array[left_node], &array[right_node]);     // 比较并交换左右结点，使左结点大于右结点            cas(&array[j], &array[left_node]);            cas(&array[left_node], &array[right_node]);        }    }    for (int i = 0; i < 15; i++)    {           cout << array[i] << " ";        if (i == 0 || i == 2 || i == 6)        {   cout << endl;}    }    }int cas(int *num1, int *num2){       if (*num1 < *num2)    {           int temp = *num1;        *num1 = *num2;        *num2 = temp;    }    return 0;}

规律发现！

顺便附带一些之前用到的图表

考虑用log函数，由于
$$lo{g}_{2}x=\frac{lgx}{lg2}$$

    int x;    cin >> x;    cout << "log(x) = " << log(x) << endl;    cout << "log(2) = " << log(2) << endl;    cout << "log_2_x = " << log(x) / log(2) << endl;    cout << "log2(x) = " << log2(x) << endl;

/* 试着写一个最大堆 */#include <iostream>#include <math.h>using namespace std;int cas(int *, int *);int main(){       int array[15];    int height = 4;    for (int i = 0; i < 15; i++)    {           cin >> array[i];    }    for (int i = 0; i < height; i++)    {           for (int j = 6; j >= 0; j--)        {               // parent_node = j            int left_node = 2 * j + 1;            int right_node = left_node + 1;            cas(&array[left_node], &array[right_node]);     // 比较并交换左右结点，使左结点大于右结点            cas(&array[j], &array[left_node]);            cas(&array[left_node], &array[right_node]);        }    }    for (int i = 0; i < 15; i++)    {           cout << array[i] << " ";        if ((int)log2(i) == log2(i) && i !=1 || i == 0)        {               cout << endl;        }    }    }int cas(int *num1, int *num2){       if (*num1 < *num2)    {           int temp = *num1;        *num1 = *num2;        *num2 = temp;    }    return 0;}

用log美化输出失败……

呜呜呜

/*    判断一位数的二进制数是否末尾为0，其他位为1*/#include <iostream>using namespace std;int main(){       for (int i = 1; i <= 20; i++)   // judge parity    {           cout << ((i & (i + 1)) == i ? i : 0 ) << " ";    }        // 20 --> 10100     // 21 --> 10101    //  & --> 10100    // 16 --> 10000    // 17 --> 10001    //  & --> 10000    //  7 --> 0111     //  8 --> 1000    //  & --> 0000        // 14 --> 0110    // 15 --> 0111    //  & --> 0110    // 2^1 --> 2 --> 0010    // 2^2 --> 4 --> 0100    // 2^3 --> 8 --> 1000    // 2^1 - 2 --> 0 --> 0000    // 2^2 - 2 --> 2 --> 0010    // 2^3 - 2 --> 6 --> 0110    // 2^4 - 2 --> 14 -->  1110    return 0;}