数据结构与算法(四):二叉堆 和 优先队列

本篇是上篇 数据结构与算法(三):树 和 二叉树 的延续。

二叉堆 是一种特殊的堆,本质上是一种完全二叉树。二叉堆有两个类型:最大堆最小堆

优先队列中,元素被赋予优先级。当访问元素时,具有最高优先级的元素最先删除。优先队列具有最高级先出 (first in, largest out)的行为特征。通常采用堆数据结构来实现。

二叉堆

最大堆

最大堆:任何一个父节点的值,都 大于等于 它左、右子节点的值,堆顶 是整个堆中的 最大 元素。

最小堆

最小堆:任何一个父节点的值,都 小于等于 它左、右孩子节点的值,堆顶 是整个堆中的 最小 元素。

二叉堆的操作

二叉堆的操作主要有 插入删除构建 三种操作。二

二叉堆的操作都基于堆的 自我调整 。所谓堆的自我调整,就是把一个不符合堆性质的完全二叉树,通过上浮 或 下沉 的方式调整成一个堆。

二叉堆 是实现 堆排序优先队列 的基础。

插入节点

从末尾插入节点,插入的节点和需要和父节点进行比较:

  • 如果是最大堆,插入节点大于父节点,插入节点上浮直到小于父节点不上浮。

  • 如果是最小堆,插入节点小于父节点,插入节点上浮直到大于父节点不上浮。

删除节点

删除节点和插入节点的过程正好相反,所删除的是处于堆顶的节点。

删除堆顶节点,把堆的最后一个元素补充到堆顶的位置,然后于左、右子节点比较,根据是最大堆或最小堆来判断是否下沉。

构建二叉堆

构建二叉堆,就是把一个无序的完全二叉树调整为二叉堆,本质是让所有 非叶子节点依次 “下沉”。

非叶子节点与左、右子节点比较,根据最大堆或最小堆来决定是否下沉。

堆的插入操作是插入节点的上浮,删除操作是插入节点的下沉。

这两个操作的平均交换次数都是堆高度的一半,所以时间复杂度是 Ο(logn) ,而构建堆的时间复杂度是 Ο*(n*) 。

二叉堆代码实现

二叉堆虽然是一个完全二叉树,但存储方式是顺序存储,而不是链式存储。在存储的物理结构上是采用数组存储。

一个数组中,在没有左、右指针的情况下,首先将数组最后一个元素(right = array.length - 1) 作为最后的叶子节点,再确定一个父节点的下标(parent = (right - 1) / 2),那它的左节点就是 left = parent * 2 + 1,右子节点就是 right = parent * 2 + 2 。

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
package com.datastructure.alg.binaryheap;

import java.util.Arrays;

/**
* 二叉堆创建与操作
*/
public class BinaryHeap {

/**
* 下沉 调整
*
* @param array 待调整的堆
* @param parentIndex 父节点索引
* @param length 堆大小
*/
public static void downAdjust(int[] array, int parentIndex, int length) {
//保存父节点值,用于最后赋值
int temp = array[parentIndex];
int childIndex = 2 * parentIndex + 1;
while (childIndex < length) {
//如果有右子节点,且右子节点小于左子节点的值,则定位到右子节点
if (childIndex + 1 < length && array[childIndex + 1] < array[childIndex]) {
childIndex++;
}

if (temp <= array[childIndex]) {
break;
}

array[parentIndex] = array[childIndex];
parentIndex = childIndex;
childIndex = 2 * childIndex + 1;
}
array[parentIndex] = temp;
}

/**
* 构建堆
*
* @param array
*/
public static void buildHeap(int[] array) {

for (int i = (array.length - 2) / 2; i >= 0; i--) {
//数组取半求父节点的索引 -1, 给最后的右页子节点留位置 -1,
//从最后一个非叶子节点开始,做依次下沉调整
downAdjust(array, i, array.length);
System.out.println("遍历:" + Arrays.toString(array));
}
}

public static void main(String[] args) {
int[] array = new int[]{4, 2, 11, 10, 8, 3, 9, 1, 5, 6, 7};
System.out.println("原始:" + Arrays.toString(array));
buildHeap(array);
System.out.println("最终:" + Arrays.toString(array));
//最终:[1, 2, 3, 4, 6, 11, 9, 10, 5, 8, 7]
}
}

优先队列

普通队列是一种是先进先出(FIFO)的数据结构。入队列,新元素在队列尾追加;出队列,队头元素最先被移出。

优先队列,元素被赋予优先级。当访问元素时,具有最高优先级的元素最先删除。优先队列具有最高级先出 (first in, largest out)的行为特征。通常采用堆数据结构来实现。

特点

优先队列则不再遵循先入先出的原则,而是分为两种情况:

  • 最大优先队列,无论入队顺序如何,都是当前最大的元素优先出队。
  • 最小优先队列,无论入队顺序如何,都是当前最小的元素优先出队。

例如,有一个最大优先队列,可能最大元素并不是队头元素,但出队时仍然是此最大元素首先出队。

基于二叉堆的特性,即最大堆的堆顶是整个堆中的最大元素,最小堆的堆顶是整个堆中的最小元素。

因此,可以用最大堆来实现最大优先队列,每一次入队操作就是堆的插入操作,每一次出队操作就是删除堆顶节点。

入队

入队:就是插入节点的操作,在堆的末尾插入,与父节点比较,大于则上浮到合适位置。

出队

出队:就是堆顶节点的删除操作,然后把最后一个节点替换到堆顶位置,再与左、右子节点比较,如果子节点更大则上浮。

二叉堆节点 上浮下沉 的时间复杂度都是 Ο(logn) ,所以优先队列入队和出队的时间复杂度也是 Ο(logn) 。

代码实现

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
import java.util.Arrays;

public class PriorityQueue {

private int[] array;
private int size;

public PriorityQueue() {
//队列初始长度为 32
this.array = new int[32];
}

/**
* 入队
*
* @param key
*/
public void enQueue(int key) {
if (size >= array.length) {
resize();
}
array[size++] = key;
upAdjust();
}

/**
* 出队
*/
public int deQueue() throws Exception {
if (size <= 0) {
throw new Exception("the queue is empty");
}

//获取堆顶元素
int head = array[0];
//让最后一个元素移动到堆顶
array[0] = array[--size];
downAdjust();
return head;
}

/**
* 上浮调整
*/
private void upAdjust() {
int childIndex = size - 1;
int parentIndex = childIndex / 2;
// temp 保存插入的叶子节点值,用于最后的赋值
int temp = array[childIndex];
while (childIndex > 0 && temp > array[parentIndex]) {
//无须真正交换,单向赋值即可
array[childIndex] = array[parentIndex];
childIndex = parentIndex;
parentIndex = parentIndex / 2;
}
array[childIndex] = temp;

}

/**
* 下沉调整
*/
private void downAdjust() {
int parentIndex = 0;
int temp = array[parentIndex];
int childIndex = 1;
while (childIndex < size) {
if (childIndex + 1 < size && array[childIndex + 1] > array[childIndex]) {
childIndex++;
}

if (temp >= array[childIndex])
break;

array[parentIndex] = array[childIndex];
parentIndex = childIndex;
childIndex = 2 * childIndex + 1;
}
array[parentIndex] = temp;
}

/**
* 队列扩容
*/
private void resize() {
//队列容量翻倍
int newSize = this.size * 2;
this.array = Arrays.copyOf(this.array, newSize);
}

public static void main(String[] args) throws Exception {
PriorityQueue priorityQueue = new PriorityQueue();
priorityQueue.enQueue(3);
priorityQueue.enQueue(5);
priorityQueue.enQueue(10);
priorityQueue.enQueue(2);
priorityQueue.enQueue(7);

System.out.println("出队元素:" + priorityQueue.deQueue());
System.out.println("出队元素:" + priorityQueue.deQueue());
}
}

更多参考

  1. 二叉堆(三)之 Java的实现
  2. 数据结构与算法系列 目录 此系列博文非常不错。

数据结构与算法(四):二叉堆 和 优先队列

http://blog.gxitsky.com/2019/07/21/DataStructure-04-binary-heap-priority-queue/

作者

光星

发布于

2019-07-21

更新于

2022-06-17

许可协议

评论