摘要: 堆排序算法

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

（二叉）堆結(jié)構(gòu)是一種數(shù)組對(duì)象，它可以被視為一顆完全二叉樹(shù)。算法時(shí)間復(fù)雜度O(nlgn)，具有插入排序和合并排序的優(yōu)點(diǎn)。堆結(jié)構(gòu)滿足堆性質(zhì)：對(duì)除根以外的每個(gè)節(jié)點(diǎn)i,滿足A[PARENT(i)] >= A[i]。

堆排序算法實(shí)現(xiàn)有三個(gè)部分完成：
1，保持堆性質(zhì)函數(shù)heap_ify;
2,構(gòu)建堆函數(shù)build_heap;
3,堆排序函數(shù) heap_sort;
另外，在優(yōu)先級(jí)隊(duì)列中有extract-max 過(guò)程和insert過(guò)程，在作業(yè)隊(duì)列中常用，比如消息隊(duì)列。這部分在優(yōu)先級(jí)排序中說(shuō)明。
  閱讀全文