logo头像

待到风起时,扬帆济沧海

二叉堆

堆和二叉堆的介绍

堆的定义

堆(heap),这里所说的堆是数据结构中的堆,而不是内存模型中的堆。堆通常是一个可以被看做一棵树,它满足下列性质:

  • 堆中任意节点的值总是不大于(不小于)其子节点的值
  • 堆总是一棵完全树。
    将任意节点不大于其子节点的堆叫做最小堆小根堆,而将任意节点不小于其子节点的堆叫做最大堆大根堆。常见的堆有二叉堆、左倾堆、斜堆、二项堆、斐波那契堆等等。

二叉堆的定义

二叉堆是完全二元树或者是近似完全二元树,它分为两种:最大堆最小堆

最大堆:父结点的键值总是大于或等于任何一个子节点的键值;最小堆:父结点的键值总是小于或等于任何一个子节点的键值。

二叉堆一般都通过”数组”来实现,下面是数组实现的最大堆和最小堆的示意图:
2.jpg

二叉堆一般都通过”数组“来实现。数组实现的二叉堆,父节点和子节点的位置存在一定的关系。有时候,我们将”二叉堆的第一个元素”放在数组索引0的位置,有时候放在1的位置。当然,它们的本质一样(都是二叉堆),只是实现上稍微有一丁点区别。

假设”第一个元素”在数组中的索引为 0 的话,则父节点和子节点的位置关系如下:

  • 索引为i的左孩子的索引是 (2*i+1);
  • 索引为i的右孩子的索引是 (2*i+2);
  • 索引为i的父结点的索引是 floor((i-1)/2);
    3.jpg
    假设”第一个元素”在数组中的索引为 1 的话,则父节点和子节点的位置关系如下:
  • 索引为i的左孩子的索引是 (2*i);
  • 索引为i的左孩子的索引是 (2*i+1);
  • 索引为i的父结点的索引是 floor(i/2);
    4.jpg

二叉堆的图文解析

在前面,我们已经了解到:”最大堆”和”最小堆”是对称关系。这也意味着,了解其中之一即可。本节的图文解析是以”最大堆”来进行介绍的。

二叉堆的核心是”添加节点”和”删除节点”,理解这两个算法,二叉堆也就基本掌握了。下面对它们进行介绍。

添加

假设在最大堆[90,80,70,60,40,30,20,10,50]种添加85,需要执行的步骤如下:
5.jpg

删除

假设从最大堆[90,85,70,60,80,30,20,10,50,40]中删除90,需要执行的步骤如下:
6.jpg
从[90,85,70,60,80,30,20,10,50,40]删除90之后,最大堆变成了[85,80,70,60,40,30,20,10,50]。
如上图所示,当从最大堆中删除数据时:先删除该数据,然后用最大堆中最后一个的元素插入这个空位;接着,把这个“空位”尽量往上挪,直到剩余的数据变成一个最大堆。

注意:考虑从最大堆[90,85,70,60,80,30,20,10,50,40]中删除60,执行的步骤不能单纯的用它的子节点来替换;而必须考虑到”替换后的树仍然要是最大堆”!
7.jpg
转换规则如索引计算规则一样即可,然后数组往前移动

最大堆完整代码

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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
package heap

type BinaryHeap struct {
Array []int //切片存储
}

/**
返回数据在数组中的索引
*/
func (this *BinaryHeap) GetIndex(data int) int {
i := 0
for i = 0; i < len(this.Array); i++ {
if data == this.Array[i] {
return i
}
}
return -1
}

/*
* 最大堆的向下调整算法
*
* 注:数组实现的堆中,第N个节点的左孩子的索引值是(2N+1),右孩子的索引是(2N+2)。
*
* 参数说明:
* start -- 被下调节点的起始位置(一般为0,表示从第1个开始)
* end -- 截至范围(一般为数组中最后一个元素的索引)
*/

func (this *BinaryHeap) filterdown(start, end int) {
current := start // 当前(current)节点的位置
left := 2*current + 1 // 左(left)孩子的位置
tmpValue := this.Array[current] // 当前(current)节点的大小
for left < end {
// "left"是左孩子,"left+1"是右孩子
if left < end && this.Array[left] < this.Array[left+1] {
left++ // 左右两孩子中选择较大者,即mHeap[left+1]
}
if tmpValue >= this.Array[left] { //调整结束
break
} else {
this.Array[current] = this.Array[left]
current = left
left = 2*left + 1
}
}
this.Array[current] = tmpValue
}

/**
删除最大堆的值
*/
func (this *BinaryHeap) Remove(data int) int {
// 如果"堆"已空,则返回-1
if len(this.Array) == 0 {
return -1
}
// 获取data在数组中的索引
index := this.GetIndex(data)
if index == -1 {
return -1
}
size := len(this.Array)
this.Array[index] = this.Array[size-1] // 用最后元素填补
this.Array = this.Array[:size-1] // 删除最后的元素
if len(this.Array) > 1 { // 从index号位置开始自上向下调整为最小堆
this.filterdown(index, len(this.Array)-1)
}
return 0
}

/*
* 最大堆的向上调整算法(从start开始向上直到0,调整堆)
*
* 注:数组实现的堆中,第N个节点的左孩子的索引值是(2N+1),右孩子的索引是(2N+2)。
*
* 参数说明:
* start -- 被上调节点的起始位置(一般为数组中最后一个元素的索引)
*/
func (this *BinaryHeap) filterup(start int) {
current := start // 当前(current)节点的位置
parent := (current - 1) / 2 // 父(parent)结点的位置
tmpValue := this.Array[current] // 当前(current)节点的大小
for current > 0 {
if this.Array[parent] >= tmpValue {
break
} else {
this.Array[current] = this.Array[parent]
current = parent
parent = (parent - 1) / 2
}
}
this.Array[current] = tmpValue
}

func (this *BinaryHeap) Add(data ...int) {
size := len(this.Array)
this.Array = append(this.Array, data...)
this.filterup(size)
}

评论系统未开启,无法评论!