实现从小到大（从大到小）排序，建立大顶堆（小顶堆）
建立大顶堆（小顶堆反之）的思路：
1.建立初始堆。（将二叉堆调整成父节点大于其孩子节点，从数组最后一个元素（二叉树最下面最右边的节点）的父亲节点开始调整）
2.每次将跟节点的值和数组最后一个元素（二叉树最下面最右边的节点）互换，舍弃最后一个元素（原来为大顶堆根节点，也就是数组最大的数放到了数组的最后）
#include <iostream> #include <vector> #include <cstdio> using namespace std; const int MAXN = 100005; void adjust(vector <int> &a, int start, int len) { int fa=start; int son=fa*2+1; while(son<len) { if(son+1<len&&a[son+1]>a[son]) son++; if(a[fa]>a[son]) return ; swap(a[fa], a[son]); fa=son; son=fa*2+1; } } void sort_heap(vector <int> &a, int len) { for(int i=len/2-1;i>=0;--i)//建立初始堆,len/2-1来由是因为最深层的最右节点的序号是len-1 而他的父节点为 (len-1)/2-1 adjust(a, i, len); for(int i=len-1;i>0;--i)//每次pop出最大的元素，放到数组最后，对剩下的二叉堆（不包括弹出的节点）进行调整 { swap(a[i], a[0]); adjust(a,0, i); } } int main() { int n, x; scanf("%d", &n); vector<int> heap; for(int i=0;i<n;++i)//从0开始，意味着左孩子是i*2+1，右孩子是i*2+2 { scanf("%d", &x); heap.push_back(x); } sort_heap(heap, n); for(int i=0;i<n;++i) printf("%d%c", heap[i], i==n-1?'\n':' '); return 0; }