第六章 優(yōu)先隊(duì)列(堆)
1. 基本概念
一種特殊的隊(duì)列，至少支持兩種操作：Insert和DeleteMin；前者插入元素，相當(dāng)于隊(duì)列的enqueue,后者查找、刪除、返回最小的元素，相當(dāng)于隊(duì)列的dequeue。
2. 二叉堆
概念
具有結(jié)構(gòu)性質(zhì)和堆序性質(zhì)的二叉樹（或者說具有堆序性質(zhì)的完全二叉樹）
性質(zhì)
- 結(jié)構(gòu)性質(zhì)：完全二叉樹
- 堆序性質(zhì)：父節(jié)點(diǎn)小于任意子節(jié)點(diǎn)
實(shí)現(xiàn)方法
數(shù)組即可， 鑒于其完全二叉樹的性質(zhì)，乘以2可以到達(dá)左子節(jié)點(diǎn)，除以2可以到達(dá)父節(jié)點(diǎn)。
操作及其時(shí)間復(fù)雜度：（后面四種操作需要節(jié)點(diǎn)位置信息為基礎(chǔ)）
- Insert: 采用上濾，最壞為O(logN)，平均只要比較2.607次，上移1.607層，O（1）
- DeleteMin: 采用下濾，最壞為O(logN)，平均為O(logN)
- DecreaseKey:
- IncreaseKey:
- Delete:
- BuildHeap: 空堆N個(gè)Insert操作來完成，總運(yùn)行時(shí)間O（N）
3. d堆
- 類似二叉堆，只是節(jié)點(diǎn)的兒子數(shù)都是d個(gè)（除了最底層的一些節(jié)點(diǎn)）。
- 有證據(jù)顯示，4堆在實(shí)踐中可以勝過二叉堆。
4.左式堆
概念
具有堆序性質(zhì)和和零路徑長(zhǎng)相關(guān)的結(jié)構(gòu)性質(zhì)的二叉樹。
性質(zhì)
- 堆序性質(zhì)：父節(jié)點(diǎn)小于任意子節(jié)點(diǎn)；
- 結(jié)構(gòu)性質(zhì)：左兒子節(jié)點(diǎn)的零路徑長(zhǎng)不小于右兒子節(jié)點(diǎn)的零路徑長(zhǎng)。（=>N個(gè)節(jié)點(diǎn)的左式堆右路徑上節(jié)點(diǎn)不超過[log(N+1)]）
實(shí)現(xiàn)方法
采用二叉樹的實(shí)現(xiàn)方法，每個(gè)節(jié)點(diǎn)增加零路徑長(zhǎng)域。
操作及其實(shí)踐復(fù)雜度
- Merge：從由路徑節(jié)點(diǎn)入手，O（logN)
- Insert：合并一個(gè)節(jié)點(diǎn)左式堆，O（logN)
- DeleteMin：O（logN)
5. 斜堆
概念
具有堆序的二叉樹，但不具有結(jié)構(gòu)性質(zhì)；其基本操作Merge和左氏堆一致，但是右路徑上的節(jié)點(diǎn)左右兒子的交換是無條件的（除了右路徑上最大節(jié)點(diǎn)不交換其左右兒子）
操作
- Merge：任意單次操作最壞時(shí)間O（N），攤還時(shí)間O（logN）
- ...
6. 二項(xiàng)隊(duì)列（binomial queue）
概念
具有堆序的二項(xiàng)樹的集合（森林）。
操作
- Merge： O（logN）
- Insert：O（logN)；從空堆連續(xù)N次插入總最壞時(shí)間O（N）
- Delete：O（logN）
