堆

定义堆 const int maxn = 100; int heap[maxn],n = 10;//n为元素个数 建堆 设叶子节点个数为n0，度为1的节点个数为n1，度为2的节点个数为n2，必有 n0+n1+n2 = n (1) 对于二叉树有： n0 = n2+1 (2) 由上面两式 ==> n0 = (n+1-n1)/2 (3) 由完全二叉树的性质可知：n1 = 0 或 1

所以完全二叉树叶子结点个数为$\lceil n/2\rceil$

于是我们可以通过从$\lfloor n/2\rfloor$号位开始倒着枚举结点建堆，保证每个结点都是以其为根节点的子树中权值最大的点

void createHeap(){ for(int i = n/2; i >= 1; i--){ downAdjust(i,n); } } //对heap数组在[low，high]范围进行下沉 //其中low为欲调整结点的数组下标，high为堆的最后一个元素的数组下标 void downAdjust(int low, int high){ int i = low, j = i * 2;//i为欲调整结点，j为左孩子 while(j <= high){ //如果又孩子存在，且右孩子的值大于左孩子 if(j + 1 <= high && heap[j + 1] > heap[j]){ j = j+1;//让j存储右孩子的下标 } //如果孩子中最大的全职比欲调整结点大 if(heap[j] > heap[i]){ swap(heap[i],heap[j]); i = j;//保持i为欲调整结点，j为i的左孩子 j = i * 2; } else{ break;//孩子的权值都比欲调整结点i小，结束 } } } 删除与插入 void deleteTop(){ heap[1] = heap[n--]; downAdjust(1,n); } void insert(int x){ heap[n++] = x; upAdjust(1,n); } //对heap数组在[low，high]范围进行上浮 //其中low一般设置为1，high表示欲调整结点的数组下标 void upAdjust(int low, int high){ int i = high,j = i /2;//i为欲调整结点，j为父结点 while(j >= low){ if(heap[j] < heap[i]){ i = j; j = i / 2; } else{ break; } } } 堆排序 void heapSort(){ createHeap(); //建堆 for(int i = n; i >= 1; i--){//倒着枚举，直到堆中只有一个元素 swap(heap[1],heap[i]);//交换heap[i]与堆顶 downAdjust(1,i - 1);//调整堆顶 } }