堆排（Heap Sort）

---

1、概念

完全二叉樹(shù)特點(diǎn)：

對(duì)于完全二叉樹(shù)中任一點(diǎn) i：

• 左孩子的位置為： 2i
• 右孩子的位置為：2i+1
• 父節(jié)點(diǎn)位置為：i/2 向下取整

最小二叉堆：根節(jié)點(diǎn)的值小于子樹(shù)的任一元素，對(duì)于子樹(shù)也一樣。

堆排實(shí)現(xiàn)：最小二叉堆，優(yōu)先隊(duì)列

---

2、插入元素

原理：在末尾插入，根據(jù)大小關(guān)系進(jìn)行調(diào)整。

插入14：

復(fù)雜度：

• 插入一個(gè)元素平均比較次數(shù)為2.607，移動(dòng)1.607層。
• 一次插入復(fù)雜度為平均為O(1)，最差為O(logN)。

---

3、刪除最小元素

原理：刪除根節(jié)點(diǎn)，其它元素依次向上補(bǔ)空。

刪除：

復(fù)雜度： O(logN)

---

4、排序

時(shí)間復(fù)雜度為O(N logN)

逐個(gè)插入，建立二叉堆，O(N)

依次刪除最小元素，O(N logN)

刪除的元素依次存入新的數(shù)組，即得到升序數(shù)組

---

總結(jié)

以上是生活随笔為你收集整理的数据结构与算法（C++）– 堆排（Heap Sort）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。