二叉树

二叉树是一个特殊结构的树。其特征为根结点必须有两个子节点，更加严格的递归定义是：二叉树要么为空；要么由根结点、左子树和右子树组成。
二叉树中有两种特殊结构的二叉树“满二叉树”和“完全二叉树”。

• “满二叉树”：如果二叉树的两个内部结点又都有两个子结点。定义深度为h的二叉树且有2的h次方-1个结点。

• “完全二叉树”：如果二叉树的左子树的子结点是满的，而右子树的子结点缺失一个或者几点子结点。

• “堆”是一种特殊的“完全二叉树”

• “最小堆”：即所有的父结点都比子结点要小，堆顶(根结点）1号结点比所有结点都小。

• （log）对数：计算以2为底的对数时：log2（6） = log6/log2

建立一个堆

/*建立一个堆，首先将这n个结点自上到下、自左到右进行1到n的编序，将堆转换成完全二叉树，紧接着从最后一个非叶结点（编号为n/2）开始到根结点（编号为1），逐个扫描所有的结点，根据需要将当前结点向下调整，直到符合特性。*/
for(i = n/2; i >= 1; i--)
     siftdown(i);

堆排序

从小到大排序，建立最大堆。
建立好最大堆，最大元素在堆顶(h[1]),因为我们的需求是从小到大排序，希望最大的放在最后，因此将h[1]和h[n]进行交换，此时h[n]就是最大的元素，请注意，交换后还需将h[1]向下调整以保持堆的特性。

void heapsort()
{
     while(n > 1)
      {
         swap(1, n);
         n--;
         siftdown;  
       }
return;
}