摘要: 堆排序算法

---------- C++博客 Alex-Lee 2009-10-15

（二叉）堆结构是一种数组对象，它可以被视为一颗完全二叉树。算法时间复杂度O(nlgn)，具有插入排序和合并排序的优点。堆结构满足堆性质：对除根以外的每个节点i,满足A[PARENT(i)] >= A[i]。

堆排序算法实现有三个部分完成：
1，保持堆性质函数heap_ify;
2,构建堆函数build_heap;
3,堆排序函数 heap_sort;
另外，在优先级队列中有extract-max 过程和insert过程，在作业队列中常用，比如消息队列。这部分在优先级排序中说明。
  阅读全文