1、生成堆
头尾交换
去头heapify
堆满足两个要求：完全二叉树，父节点大于子节点
heapify:d=堆化
如果是一个顺序混乱的堆，从倒数第二层做heapify
#include <stdio.h> void swap(int arr[], int i, int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } void heapify(int tree[], int n, int i) { if(i >= n) return;//递归函数出口 int c1 = 2*i + 1;//right int c2 = 2*i + 2;//left int max = i; if(c1 < n && tree[c1] > tree[max]) { max = c1; } if(c2 < n && tree[c2] > tree[max]) { max = c2; } if(max != i) { swap(tree, max, i);//对max和i对应的值做交换 heapify(tree, n, max); } } void build_heap(int tree[], int n) { int last_node = n - 1;//最后一个节点 int parent_node = (last_node - 1)/2; int i; for(i = parent_node; i >= 0; i--)//从最后一个开始 { heapify(tree, n, i); } } void heap_sort(int tree[], int n) { build_heap(tree,n); for(int i = n-1; i >= 0; i--) { swap(tree,i,0); heapify(tree, i, 0); } } int main(){ int tree[] = {2,5,3,1,10,4}; int n = 6; //heapify(tree, n, 0); heap_sort(tree, n); int i; for(i = 0; i < n; i++) { printf("%d\n",tree[i]); } return 0; }
