堆：堆(Heap)是一类特殊的数据结构的统称。堆通常是一个可以被看做一棵完全二叉树的数组对象。
堆总是满足下列性质：
堆中某个节点的值总是不大于或不小于其父节点的值；
堆总是一棵完全二叉树。
完全二叉树：叶子结点只能出现在最下层和次下层，且最下层的叶子结点集中在树的左部。
注意：满二叉树肯定是完全二叉树，而完全二叉树不一定是满二叉树。
对某个节点堆化：
程序实现：
#includeiostreamusingnamespacestd;voidswap(inttree[],inti,intj){inttemp=tree;tree=tree[j];tree[j]=temp;}//堆化函数，如果数组编号从0开始，那么左子树left编号对应2*i+1、右子树right编号对应2*i+2voidheapify(inttree[],intn,inti){//左子树编号intleft=2*i+1;//右子树编号intright=2*i+2;//如果满足条件，left和i对比交换,必须建立在i的左子树必须存在的情况下，也就是leftnif(leftntreetree[left]){swap(tree,i,left);//重新回归到左子树重复对left进行条件判断，判断是否需要堆化heapify(tree,n,left);}//如果满足条件，right和i对比交换，必须建立在i的右子树必须存在的情况下，也就是rightnif(rightntreetree[right]){swap(tree,i,right);//重新回归到左子树重复对left进行条件判断，判断是否需要堆化heapify(tree,n,right);}}intmain(){//数组测试inttree[6]={5,10,3,4,1,2};heapify(tree,6,0)for(inti=0;i6;i++){couttree"";}return0;}
堆重建：
程序实现：
#includeiostreamusingnamespacestd;voidswap(inttree[],inti,intj){inttemp=tree;tree=tree[j];tree[j]=temp;}voidheapify(inttree[],intn,inti){intleft=2*i+1;intright=2*i+2;if(leftntreetree[left]){swap(tree,i,left);heapify(tree,n,left);}if(rightntreetree[right]){swap(tree,i,right);heapify(tree,n,right);}}//堆重建函数,for循环遍历从下往上对子堆进行定点i堆化voidheap_build(inttree[],intn){//拿到最后一个节点位置intlast_node=n-1;//根据公式推父节点位置intparent=(last_node-1)/2;//for循环遍历从下往上对子堆进行定点i堆化for(inti=parent;i=0;i--){heapify(tree,n,i);}}intmain(){//数组测试inttree[6]={5,4,2,10,1,3};heap_build(tree,6);for(inti=0;i6;i++){couttree"";}return0;}
堆排序：
第一步：对数组数据进行堆重建
第二步：遍历末尾元素，将堆顶元素和末尾元素发生位置交换
第三步：每交换一次，重新堆化，方便下次堆顶与末尾元素交换
#includeiostreamusingnamespacestd;voidswap(inttree[],inti,intj){inttemp=tree;tree=tree[j];tree[j]=temp;}voidheapify(inttree[],intn,inti){intleft=2*i+1;intright=2*i+2;if(leftntreetree[left]){swap(tree,i,left);heapify(tree,n,left);}if(rightntreetree[right]){swap(tree,i,right);heapify(tree,n,right);}}voidheap_build(inttree[],intn){intlast_node=n-1;intparent=(last_node-1)/2;for(inti=parent;i=0;i--){heapify(tree,n,i);}}//堆排序voidheap_sort(inttree[],intn){//第一步：堆重建heap_build(tree,n);//第二步：遍历末尾元素for(inti=n-1;i=0;i--){//遍历末尾元素，和堆顶元素互换，每交换一次，i向前移动一步swap(tree,i,0);//第三步:重新堆化,方便下次交换heapify(tree,i,0);}}intmain(){//数组测试inttree[6]={5,4,2,10,1,3};heap_sort(tree,6);for(inti=0;i6;i++){couttree"";}return0;}一只小跃跃