二叉堆，簡(jiǎn)稱堆 Heap
尖的完全二叉樹。也有三叉堆以及普通堆，但大部分時(shí)候堆就是指二叉堆
- 二叉堆的定義
一棵完全二叉樹
父節(jié)點(diǎn)的值 >= 子節(jié)點(diǎn)的值，則稱為最大二叉堆父節(jié)點(diǎn)的值 <= 子節(jié)點(diǎn)的值，則稱為最小二叉堆
注意：并沒有要求左右節(jié)點(diǎn)的大小順序
- 舉例
[35，26，48，10，59，64，17，23，45，31]
image.png
最大堆的性質(zhì)
- 堆序性 heap order
任意節(jié)點(diǎn) >= 它的所有后代，最大值在堆的根上
- 完全樹
只有最底層不滿，且節(jié)點(diǎn)盡可能的往左靠
最小堆的性質(zhì)
- 堆序性 heap order
任意節(jié)點(diǎn) <= 它的所有后代，最小值在堆的根上
- 完全樹
只有最底層不滿，且節(jié)點(diǎn)盡可能的往左靠
堆的 API
image.png
API - heapify 如何把完全二叉樹變成堆
完全二叉樹可以用數(shù)組存儲(chǔ)
思路 (siftDown)
image.png
從最后一個(gè)節(jié)點(diǎn)開始，逐個(gè)向前，把每個(gè)節(jié)點(diǎn)與其后代比較，最大的放在上面
注意一個(gè)節(jié)點(diǎn)有可能需要調(diào)整多次（遞歸）
由于每次調(diào)整都是把數(shù)字下降，所以叫 siftDown
- 代碼
const array = [35, 26, 48, 10, 59, 64, 17, 23, 45, 31]
const heapify = array => {
for (let i = parseInt((array.length - 1) / 2); i >= 0; i--) {
siftDown(array, i, array.length)
}
return array
}
siftDown = (heap, i, length) => {
const left = 2 * i + 1, right = 2 * i + 2
let greater = left
if (greater >= length) {return}
if (right < length && heap[right] > heap[greater]) {
greater = right
}
if(heap[greater]>heap[i]){
console.log(`換 ${heap[greater]} ${heap[i]}`);
[heap[greater],heap[i]] = [heap[i],heap[greater]]
siftDown(heap, greater, length)
}
}
heapify(array)
// [64, 59, 48, 45, 31, 35, 17, 23, 10, 26]
image.png
問答
- 為什么要從后往前
為了從易到難
- 為什么從 59 開始
因?yàn)樗匀~子節(jié)點(diǎn)都可以跳過
- 什么時(shí)候遞歸
調(diào)整父子之后，子節(jié)點(diǎn)所在的子樹要再調(diào)整一次
API - insert(heap, item) 如何向堆中插入一個(gè)值
要保證插入之后，依然得到一個(gè)堆
思路 (siftUp)
image.png
- 代碼
const heap = [64,59,48,45,31,35,17,23,10,26]
const insert = (heap, item) => {
heap.push(item) // 把新值放到最后一個(gè)
siftUp(heap, heap.length-1) // 開始上升
}
siftUp = (heap, i) => {
if(i===0){return}
const parent = parseInt((i-1)/2)
if(heap[i]>heap[parent]){
console.log(`換 ${heap[i]} ${heap[parent]}`);
[heap[i],heap[parent]]=[heap[parent],heap[i]]
siftUp(heap, parent)
} }
insert(heap, 60)
console.log(heap) // [64, 60, 48, 45, 59, 35, 17, 23, 10, 26, 31]
image.png
API - extractMax(heap) 如何彈出堆頂?shù)闹?/h1>
要保證彈出后，剩下的元素依然組成堆
思路 (extractMax)
image.png
- 代碼
const heap = [64, 60, 48, 45, 59, 35, 17, 23, 10, 26, 31]
const extractMax = (heap, start, end) => {
[heap[start], heap[end - 1]] = [heap[end - 1], heap[start]]
const max = heap[end - 1]
siftDown(heap, start, end - 1) // 將 start 沉下去
return max
}
const siftDown = (heap, i, length) => {
const left = 2 * i + 1,
right = 2 * i + 2
let greater = left
if (greater >= length) return
if (right < length && heap[right] > heap[greater]) {
greater = right
}
if (heap[greater] > heap[i]) {
console.log(`交換 ${heap[greater]} ${heap[i]}`);
[heap[greater], heap[i]] = [heap[i], heap[greater]]
siftDown(heap, greater, length)
}
}
max = extractMax(heap, 0, heap.length)
heap.pop() // 刪掉最后一個(gè)多余的最大值
console.log(max, heap)
// 64, [60, 59, 48, 45, 31, 35, 17, 23, 10, 26]
image.png
堆排序
-
思路（結(jié)合前面的知識(shí)可以很簡(jiǎn)單的寫出堆排序）
image.png 代碼
array = [9,5,1,4,7,8,3,2,6]
const heapSort = arr => {
// 第一步：數(shù)組變成堆 O(N*logN)
const heap = heapify(arr)
// 第二步：不停把最大的放到最后 O(N*logN)
for(let i=0; i<heap.length-1; i++){
// extractMax 自動(dòng)把 max 放到最后
extractMax(heap,0,heap.length-i)
}
return heap
}
const heapify = array => {
for (let i = parseInt((array.length - 1) / 2); i >= 0; i--) {
siftDown(array, i, array.length)
}
return array
}
const siftDown = (heap, i, length) => {
const left = 2 * i + 1, right = 2 * i + 2
let greater = left
if (greater >= length) {return}
if (right < length && heap[right] > heap[greater]) {
greater = right
}
if (heap[greater] > heap[i]) {
console.log(`換 ${heap[greater]} ${heap[i]}`);
[heap[greater], heap[i]] = [heap[i], heap[greater]]
siftDown(heap, greater, length)
}
}
const extractMax = (heap, start, end) => {
[heap[start], heap[end - 1]] = [heap[end - 1], heap[start]]
const max = heap[end - 1]
siftDown(heap, start, end - 1) // 將 start 沉下去
return max
}
heapSort(array)
console.log(array)
// [1, 2, 3, 4, 5, 6, 7, 8, 9]
// O(2*N*logN) O(N*logN)
image.png
