前导知识

完全二叉树

每一层都从左向右填填满后才新开一层的树称为完美二叉树

完美二叉树

一棵节点值总是大于其子节点值得完美二叉树称为大顶堆

一棵节点值总是小于其子节点值得完美二叉树称为小顶堆

大顶堆
大顶堆

父子节点的关系

完美二叉树中一个节点的父子节点具有以下关系

heapify函数

将堆中唯一一个不满足堆的节点进行堆化

void swap(int tree[], int a, int b){
   int temp = tree[a];
   tree[a] = tree[b];
   tree[b] = temp;
}
void heapify(int tree[], int length, int parent){
   if(parent >= n) return;
   int childL = 2 * parent + 1;
   int childR = 2 * parent + 2;
   int max = i;
   if(childL < length && tree[childL] > tree[max]){
       max = childL;
  }
   if(childR < length && tree[childR] > tree[max]){
       max = childR;
  }
   if(max != parent){
       swap(tree, max, parent);
       //由于改变了子节点,子树的堆可能也会乱,需要对子树进行heapify
       heapify(tree, length, max);
  }
}

buildHeap函数

将一个乱序的完美二叉树构建为一个堆

从最后一个非叶节点倒过来按顺序heapify,能保证每次heapify只有该节点不满足堆。

void buildHeap(int tree[], int length){
   int lastNode = length - 1;
   int lastParent = (lastNode - 1) / 2;
   int i = lastParent;
   while(i>=0){
       heapify(tree, length, i);
       --i;
  }
}

sortHeap函数

先通过调用buildHeap将数组构造为一个堆,然后将堆进行排序。

堆中的根值肯定是最大值,故取出根的值,将尾部的值放至根值中,此时除了根植,都满足堆,因此再次进行heapify即可再次取得接下来的最大值,重复即可。

void sortHeap(int tree[], int length){
   buildHeap(tree, length);
   int i = length;
   while(i > 0){
       swap(tree, 0, length - 1);
       heapify(tree, length - 1, 0);
       --i;
  }
}

一沙一世界,一花一天堂。君掌盛无边,刹那成永恒。