堆結(jié)構(gòu)是一種數(shù)組對(duì)象，是一棵完全二叉樹(shù)。

為紅河等地區(qū)用戶提供了全套網(wǎng)頁(yè)設(shè)計(jì)制作服務(wù)，及紅河網(wǎng)站建設(shè)行業(yè)解決方案。主營(yíng)業(yè)務(wù)為成都做網(wǎng)站、成都網(wǎng)站制作、紅河網(wǎng)站設(shè)計(jì)，以傳統(tǒng)方式定制建設(shè)網(wǎng)站，并提供域名空間備案等一條龍服務(wù)，秉承以專(zhuān)業(yè)、用心的態(tài)度為用戶提供真誠(chéng)的服務(wù)。我們深信只要達(dá)到每一位用戶的要求，就會(huì)得到認(rèn)可，從而選擇與我們長(zhǎng)期合作。這樣，我們也可以走得更遠(yuǎn)！

性質(zhì)

若當(dāng)前節(jié)點(diǎn)編號(hào)為i，父結(jié)點(diǎn)則為i/2，左孩子為2i，右孩子為2i+1。

堆的結(jié)點(diǎn)數(shù)\(\le\)數(shù)組長(zhǎng)度len

下圖為一個(gè)大根堆：每個(gè)結(jié)點(diǎn)均小于其父結(jié)點(diǎn)，樹(shù)根是堆中最大的結(jié)點(diǎn)，小根堆反之。

添加

往堆中添加一個(gè)元素。

重復(fù)n次添加操作，即可建立一個(gè)小根堆。

實(shí)現(xiàn)流程（以小根堆為例）

先在堆尾加入1個(gè)元素,并把這個(gè)結(jié)點(diǎn)置為當(dāng)前結(jié)點(diǎn)。

比較當(dāng)前結(jié)點(diǎn)和它的父結(jié)點(diǎn)的大小，

如果當(dāng)前結(jié)點(diǎn)小于父結(jié)點(diǎn)，交換它們的值，把父結(jié)點(diǎn)置為當(dāng)前結(jié)點(diǎn)。

重復(fù)以上過(guò)程。

如果當(dāng)前結(jié)點(diǎn)大于等于父結(jié)點(diǎn)，結(jié)束。

取出堆頂

從堆中取出并刪除一個(gè)元素。

實(shí)現(xiàn)流程（以小根堆為例）

取出根結(jié)點(diǎn)的值。

把堆的最后一個(gè)結(jié)點(diǎn)(len)放到根的位置上，把根覆蓋掉。

把堆的長(zhǎng)度減一。

把根結(jié)點(diǎn)置為當(dāng)前結(jié)點(diǎn)。

如果當(dāng)前節(jié)點(diǎn)無(wú)兒子（pa>len/2），結(jié)束。

否則，比較當(dāng)前節(jié)點(diǎn)與其子節(jié)點(diǎn)的值，

如果當(dāng)前節(jié)點(diǎn)的值小于等于其子節(jié)點(diǎn)，結(jié)束。

反之則交換這兩個(gè)結(jié)點(diǎn)的值，重復(fù)上述步驟，直至結(jié)束。

優(yōu)先隊(duì)列

priority_queue

Type是數(shù)據(jù)類(lèi)型，Container是容器類(lèi)型。

（Container必須是用數(shù)組實(shí)現(xiàn)的容器，比如vector,deque等，但不能用list，STL里默認(rèn)用vector）

Functional是比較函數(shù)，當(dāng)需要用自定義的數(shù)據(jù)類(lèi)型時(shí)才需要傳入這三個(gè)參數(shù)，使用基本數(shù)據(jù)類(lèi)型時(shí)，只需要傳入數(shù)據(jù)類(lèi)型，默認(rèn)是大根堆。

頭文件

include

定義小根堆

priority_queue,greater>q;//升序隊(duì)列

定義大根堆

priority_queue,less>q;//降序隊(duì)列

基本操作

empty()

如果隊(duì)列為空，則返回真。

pop()

刪除隊(duì)頭元素，即刪除第一個(gè)元素。

push(）

加入一個(gè)元素。

size()

返回優(yōu)先隊(duì)列中擁有的元素個(gè)數(shù)。

top()

返回優(yōu)先隊(duì)列隊(duì)頭元素，即優(yōu)先級(jí)最高的元素。

在默認(rèn)的優(yōu)先隊(duì)列中，優(yōu)先級(jí)高的先出隊(duì)。

在默認(rèn)的int型中先出隊(duì)的為較大的數(shù)。

堆排序

并非原創(chuàng)，僅是整理，請(qǐng)見(jiàn)諒