理解数据结构堆

发表于

基本概念

满足所有父节点都大于(小于等于)子节点的完全二叉树就是堆
其中包含两点
1.完全二叉树
2.父节点大于子节点 大/小根堆

从左向右连续非断开的二叉树就是完全二叉树
完全二叉树可以用数组表示
对于完全二叉树，对于节点i,其父节点parent = (i-1)/2
左子节点c1=2i+1,右子节点c2=2i+2

heapify操作

将当前节点作为根节点与子节点对比，将根节点设置为最大(小)的值，并对改动的子节点递归应用heapify操作

1
2
3
4
heapify(int tree[],int n,int i)
    tree为完全二叉树
    n为树的节点数量
    i为要做heapify的节点索引

对于完全无序的树如何变为堆(建堆)

由最后一个节点的父节点连续至第0个节点依次做heaplify后便得到一个堆

堆排序

对一个n个节点的堆，将最后一位与第一位调换位置，在第n-1位置上取得最大(小)的值，然后对n-1个节点进行heapify，再次调换位置，在第n-2位置上取到当前堆的最大(小)值，一直进行到第0个位置

Go实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
package main
import "fmt"
func main() {
    a := []int{3, 2, 6, 7, 1}
    heapSort(a)
    fmt.Println(a)
}
//堆排序
func heapSort(tree []int) {
    buildHeap(tree)
    n := len(tree)
    for i := n - 1; i > 0; i-- {
        swap(tree, i, 0)
        heapify(tree, i, 0)
    }
}
//建堆 (大根堆)
func buildHeap(tree []int) {
    n := len(tree)
    p := (n - 1) / 2
    for i := p; i >= 0; i-- {
        heapify(tree, n, i)
    }
}
func heapify(tree []int, n int, i int) {
    max := i
    c1 := 2*i + 1
    c2 := 2*i + 2
    if c1 < n && tree[c1] > tree[max] {
        max = c1
    }
    if c2 < n && tree[c2] > tree[max] {
        max = c2
    }
    if max != i {
        swap(tree, max, i)
        heapify(tree, n, max)
    }
}
func swap(tree []int, a int, b int) {
    tree[a], tree[b] = tree[b], tree[a]
}

FAQ

1.为什么需要buildheap，heapify后不是已经得到堆了吗？
理解有误，heapify是自定向下的，所以会出现最大数在最底下冒不上来的情况，无法保证一定可以生成堆，build_heap函数包含了heapify并且是从底层开始的，所以能生成堆

参考

http://bubkoo.com/2014/01/14/sort-algorithm/heap-sort/
https://visualgo.net/en/heap
https://www.bilibili.com/video/av47196993?from=search&seid=5370951965537253060