数据结构系列——堆

堆(Heap)是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵树的数组对象。在队列中,调度程序反复提取队列中第一个作业并运行,因为实际情况中某些时间较短的任务将等待很长时间才能结束,或者某些不短小,但具有重要性的作业,同样应当具有优先权。堆即为解决此类问题设计的一种数据结构。

堆的性质

堆的实现通过构造二叉堆(binary heap),实为二叉树的一种;由于其应用的普遍性,当不加限定时,均指该数据结构的这种实现。这种数据结构具有以下性质:

  • 任意节点小于(或大于)它的所有后裔,最小元(或最大元)在堆的根上(堆序性)。
  • 堆总是一棵完全树。即除了最底层,其他层的节点都被元素填满,且最底层尽可能地从左到右填入。
    将根节点最大的堆叫做最大堆或大根堆,根节点最小的堆叫做最小堆或小根堆。常见的堆有二叉堆、斐波那契堆等。

堆的主要应用场景有:堆排序以及优先队列

堆的表现形式

对于理解堆以及实现堆很重要的一点就是明白堆的表现形式,堆是树的一种,所以很自然的想到使用链表来实现堆,其实不然,由于我们需要频繁的对堆进行增加删除,所以一般堆的底层都是通过数组来实现,那么就有一个问题:数组如何表现出堆的结构呢?这里就有一个规则,即数组的第一个元素(即下标为0的元素)为堆的根节点,其他节点按照堆结构自上而下,自左而右依次表示为数组中的元素,这是一种既非前序也非后序,更非中序的遍历树的方式。具体见下图。

堆的数组表现形式

明白了堆如何使用数组来表述,那么我们就很容易理解下面堆的结构特征了。

  • parent(t)=(t - 1) >> 1,即t的父节点的下标=(t-1)/2,注意此处是整除,例如:t = 6,parent(t) = 2
  • left(t)=t << 1 + 1,即t的左孩子的节点下标=t * 2 + 1,例如:t = 2,left(t) = 5
  • right(t)=t << 1 + 2,即t的右孩子的节点下标=t * 2 + 2,例如:t = 2, right(t) = 6
  • 说明:此处的下标是从0开始
堆的操作

针对堆主要的操作有:

  • 构建堆:将一个数组构建成堆的结构
  • 移除堆的根节点:从堆中移除最大值(大顶堆)或者最小值(小顶堆)
  • 往堆中插入一个节点:插入节点
  • 调整堆:在对堆的结构进行修改之后需要进行的操作,以保证堆结构
堆的具体实现

下面看看一个Java版的堆的实现。

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
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
package com.vicky.datastructure.tree.heap;

import java.util.Arrays;

/**
*
* <p>
* 数据结构——树——堆
* </p>
*
* @author Vicky
* @email vicky01200059@163.com
* @2015年11月18日
*
*/

public abstract class Heap {
protected int[] data;
protected int length = 0;

public Heap(int[] data) {
this.data = data;
this.length = data.length;
}

/**
* 构建堆
*/

public abstract Heap buildHeap();

/**
* 删除一个节点,只能删除根节点
*
* @return
*/

public abstract Heap remove();

/**
* 插入一个节点,只能插入到最后
*
* @param value
* @return
*/

public abstract Heap insert(int value);

/**
* 从node开始自上而下调整堆
*
* @param node
*/

public abstract void adjustDownHeap(int node);

/**
* 从node开始自下而上调整堆
*
* @param node
*/

public abstract void adjustUpHeap(int node);

/**
* 交换元素
*
* @param n1
* @param n2
*/

public void swap(int n1, int n2) {
int temp = data[n1];
data[n1] = data[n2];
data[n2] = temp;
}

/**
* 获取node的父节点的索引
*
* @param node
* @return
*/

protected int getParentIndex(int node) {
return (node - 1) >> 1;
}

/**
* 获取node的右孩子索引
*
* @param node
* @return
*/

protected int getRightChildIndex(int node) {
return (node << 1) + 1;
}

/**
* 获取node的左孩子索引
*
* @param node
* @return
*/

protected int getLeftChildIndex(int node) {
return (node << 1) + 2;
}

/**
* 打印堆
*/

protected void print() {
System.out.println(Arrays.toString(data));
}
}

package com.vicky.datastructure.tree.heap;

import java.util.Arrays;

/**
* <p>
* 最大堆
* </p>
*
* @author Vicky
* @email vicky01200059@163.com
* @2015年11月18日
*
*/

public class MaxHeap extends Heap {
public MaxHeap(int[] data) {
super(data);
}

/**
* {@inheritDoc}
*/

public Heap buildHeap() {
// 从最后一个节点的父节点开始构建堆
int start = getParentIndex(length - 1);
for (; start >= 0; start--) {
adjustDownHeap(start);
}
return this;
}

/**
* {@inheritDoc}
*/

public Heap remove() {
// 将最后一个节点与头结点交换
swap(0, length - 1);
// 重新复制一个数组
int[] newData = new int[length - 1];
System.arraycopy(data, 0, newData, 0, length - 1);
this.data = newData;
this.length = length - 1;
// 从头开始调整堆
adjustDownHeap(0);
return this;
}

/**
* {@inheritDoc}
*/

public Heap insert(int value) {
// 插入到数组最后
int[] newData = new int[length + 1];
System.arraycopy(data, 0, newData, 0, length);
newData[length] = value;
this.data = newData;
this.length = length + 1;
// 从最后一个节点开始自下而上调整堆
adjustUpHeap(this.length - 1);
return this;
}

/**
* {@inheritDoc}
*/

public void adjustDownHeap(int node) {
int right = getRightChildIndex(node);// 右孩子
int left = getLeftChildIndex(node);// 左孩子
int max = node;// 三者最大的节点的索引
if (right < length && data[right] > data[max]) {
max = right;
}
if (left < length && data[left] > data[max]) {
max = left;
}
if (max != node) {// 需要调整
swap(node, max);
adjustDownHeap(max);// 递归调整与根节点进行交换的节点,保证下层也是堆
}
}

/**
* {@inheritDoc}
*/

public void adjustUpHeap(int node) {
int parent = getParentIndex(node);// 父节点
if (parent >= 0 && data[parent] < data[node]) {
swap(node, parent);
adjustUpHeap(parent);// 递归调整与根节点进行交换的节点,保证上层也是堆
}
}

public static void main(String[] args) {
int[] data = new int[10];
for (int i = 0; i < data.length; i++) {
data[i] = (int) (Math.random() * 100);
}
System.out.println(Arrays.toString(data));
Heap heap = new MaxHeap(data);
heap.buildHeap().print();
heap.remove().print();
heap.insert((int) (Math.random() * 100)).print();
}
}

如上代码使用了继承,首先定义了一个堆的抽象类(Heap),封装了一些堆的公用方法,如:swap/getParentIndex/getRightChildIndex/getLeftChildIndex/print,其中具体的实现跟堆相关的方法通过抽象类由子类来实现,如:buildHeap/remove/insert/adjustHeap。大顶堆(MaxHeap)继承自Heap,实现具体的大顶堆的操作。小顶堆(MinHeap)的代码就不贴了,跟大顶堆相差不大,完整代码可见:GitHub
下面结合上面的代码分别对堆的四个操作进行简单解释,都比较简单。

构建堆

首先构建堆,对于给定一个数组,我们需要将其构建成一个堆的结构,这个过程是一个递归的过程,相当于盖楼,先从最底层开始构建,并逐层往上构建,最终构建成一个完整的堆。
所以这里从最后一个节点的父节点开始构建堆,即构建最底层的堆,看图。

构建堆的过程

移除元素

从一个堆的结构中移除元素,一般都是移除堆顶元素,即最大值或者最小值,当我们移除堆顶元素之后,需要用堆的最后一个元素来填补到堆顶元素,然后这个堆的结构已经被破坏,我们需要调整这个堆,使其满足堆的结构。调整堆将在下面说。

插入元素

堆中插入元素一般是将其插入到堆的最后一个元素,然后自下而上递归调整堆。

调整堆

调整堆的方式有两种:自上而下和自下而上,分别对应移除堆和插入元素。但是两种方式的逻辑是一致的,即递归调整堆,如自上而下则寻找其两个子节点,将三者最大的放到根节点(三者小堆的根,不是整个大堆),然后递归调整移动了的节点(如右节点最大,则将右节点与根节点发生交换,递归调整右节点),最终到达底层,或者中途未发生交换则结束。自下而上原理类似,只是将一个节点与其父节点进行比较。

以上是我个人对堆的了解,如有错误请不宁赐教~

如果想了解更多关于堆的使用案例,可参考:

参考文章

堆 (数据结构)
数据结构之堆