每一秒钟的时间都值得铭记

0%

数据结构之什么是二叉堆？

发表于 分类于
本文字数： 7.5k 阅读时长 ≈ 7 分钟

什么是二叉堆？

二叉堆本质上是一种完全二叉树，它分为两个类型：

  • 最大堆
  • 最小堆

什么是最大堆？

最大堆的任何一个父节点的值，都大于或等于它的左、右孩子节点的值。

什么是最小堆？

最小堆的任何一个父节点的值，都小于或等于它的左、右孩子节点的值。

二叉堆的根节点叫做堆顶。
最大堆和最小堆的特点决定了：最大堆的堆顶是整个堆中的最大元素，最小堆的堆顶是整个堆中的最小元素。

二叉堆的自我调整

二叉堆的操作都基于堆的自我调整。所谓堆的自我调整，就是把一个不符合堆性质的完全二叉树，调整为一个堆。

本篇文章中是以最小堆为例子讲述的。

插入节点

当二叉堆插入节点时，插入的位置是二叉堆的最后一个位置，可以将新插入的节点和它的父节点进行对比，如果新节点比父节点小，就需要让新节点“上浮”，和父节点交换位置。

然后继续和父节点比较大小，直到父节点比当前节点的值小为止。

删除节点

当二叉堆删除节点时，所删除的节点是对于堆顶的节点。

然后将堆的最后一个节点补到堆顶的位置，然后对堆顶的位置的节点进行“下沉”操作

构建二叉堆

构建二叉堆，是通过一个无序的完全二叉树，对所有非叶子节点进行依次“下沉”操作，这样就得到了一个最小二叉堆。

最小二叉堆的实现

二叉堆虽然是一个完全二叉堆，但是它并不是链式存储，而是顺序存储，也就是说，二叉堆是通过数组实现的。

在数组中，在没有左、右孩子节点指针的情况下，可以通过数组下标的计算来得到一个节点的左右孩子节点。

1
2
3
4
5
6
7
       1
     /   \
    4     8
   /  \  / \
  10  7  9  13
 / \
11  19

如上图中的最小堆，在数组中的存储位置为：

1 4 8 10 7 9 13 11 19
0 1 2 3 4 5 6 7 8

如果一个节点的数组下标为current，则该节点的左孩子节点下标为2 * current + 1，该节点的右孩子节点下标为2 * current + 2，该节点的父节点下标为(current - 1) / 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
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
public class MinHeap {
    /**
     * 用于存储二叉堆的数组
     */
    private Integer[] array;
    /**
     * 当前二叉堆的最大节点个数，即数组长度
     */
    private int maxSize;

    /**
     * 当前二叉堆的节点个数
     */
    private int size;

    /**
     * 获取数组的实际元素个数
     *
     * @return 数组的实际元素个数
     */
    public int size() {
        return this.size;
    }

    /**
     * 获取数组的长度
     *
     * @return 数组的长度
     */
    public int length() {
        return this.maxSize;
    }

    /**
     * 最小堆的构造函数
     *
     * @param arr 数组
     */
    public MinHeap(Integer[] arr) {
        buildMinHeap(arr);
    }

    /**
     * 构建最小堆
     *
     * @param arr 数组
     */
    private void buildMinHeap(Integer[] arr) {
        this.size = arr.length;
        this.maxSize = arr.length;
        this.array = arr;
        // 获取最后一个节点的下标
        int lastIndex = arr.length - 1;
        // 从最后一个非叶子节点开始进行下沉
        for (int i = getParentIndex(lastIndex); i >= 0; i--) {
            downAdjust(i);
        }
    }

    /**
     * 通过孩子节点下标，获取父节点下标
     *
     * @param childIndex 孩子节点下标
     * @return 父节点下标
     */
    private int getParentIndex(int childIndex) {
        // 通过取余数的方式，直接获取左右孩子节点的父节点
        return (childIndex - 1) / 2;
    }

    /**
     * 通过父节点下标，获取左孩子节点下标
     *
     * @param parentIndex 父节点下标
     * @return 左孩子节点下标
     */
    private int getLeftChildIndex(int parentIndex) {
        return 2 * parentIndex + 1;
    }

    /**
     * 通过父节点下标，获取右孩子节点下标
     *
     * @param parentIndex 父节点下标
     * @return 右孩子节点下标
     */
    private int getRightChildIndex(int parentIndex) {
        return 2 * parentIndex + 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
/**
 * 在堆的末尾插入一个数据
 *
 * @param data 数值
 */
public void insert(int data) {
    if (size >= maxSize) {
        resize();
    }
    this.array[this.size++] = data;
    upAdjust();
}

/**
 * 数组扩容操作
 */
private void resize() {
    // 新数组的长度为原数组的2倍
    this.maxSize = this.maxSize * 2;
    // 初始化新数组
    Integer[] newArray = new Integer[maxSize];
    // 将原数组的元素复制到新数组中
    System.arraycopy(this.array, 0, newArray, 0, this.size);
    // 使用新数组替换原数组
    this.array = newArray;
}

/**
 * 上浮操作
 */
private void upAdjust() {
    // 数组最后一个节点所在的下标，即需要上浮的节点
    int currentIndex = this.size - 1;
    int parentIndex = getParentIndex(currentIndex);
    // 将当前孩子节点使用临时变量保存
    int temp = this.array[currentIndex];
    // 如果当前孩子节点的下标大于0，并且当前孩子节点的值小于父节点的值
    while (currentIndex > 0 && temp < this.array[parentIndex]) {
        // 将父节点的值和当前孩子节点的值进行交换
        this.array[currentIndex] = this.array[parentIndex];
        // 将当前孩子节点的值修改为之前的父节点的值
        currentIndex = parentIndex;
        // 维护父节点的下标
        parentIndex = getParentIndex(currentIndex);
    }
    this.array[currentIndex] = temp;
}

最小堆删除节点并下沉

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
/**
 * 移除堆顶的元素
 *
 * @return 堆顶的元素
 */
public Integer remove() {
    if (this.size == 0) {
        return null;
    }
    Integer removeData = this.array[0];
    // 获取最后一个节点
    this.array[0] = this.array[size - 1];
    downAdjust(0);
    this.array[--size] = null;
    return removeData;
}

/**
 * 下沉操作
 *
 * @param parentIndex 需要下沉的节点下标
 */
private void downAdjust(int parentIndex) {
    // 获取左孩子节点的下标
    int childIndex = getLeftChildIndex(parentIndex);
    // 将需要下沉的节点使用临时变量保存
    int temp = this.array[parentIndex];
    // 如果左孩子节点的下标还在堆的有效个数之内，
    while (childIndex < this.size) {
        // 右孩子节点为左孩子节点的下一位
        int rightChildIndex = childIndex + 1;
        // 如果有右孩子节点，并右孩子节点比左孩子节点的值小，则定位到右孩子节点
        if (rightChildIndex < this.size && this.array[rightChildIndex] < this.array[childIndex]) {
            childIndex++;
        }
        // 如果需要下沉的节点小于孩子节点中最小的那个节点的值，直接打断程序，不继续下沉
        if (temp <= this.array[childIndex]) {
            break;
        }
        // 调换父子节点的值
        this.array[parentIndex] = this.array[childIndex];
        // 将父节点的下标修改为子节点的下标
        parentIndex = childIndex;
        // 维护左孩子节点的下标
        childIndex = getLeftChildIndex(parentIndex);
    }
    this.array[parentIndex] = temp;
}

最小堆的完整代码实现

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
public class MinHeap {
    /**
     * 用于存储二叉堆的数组
     */
    private Integer[] array;
    /**
     * 当前二叉堆的最大节点个数，即数组长度
     */
    private int maxSize;

    /**
     * 当前二叉堆的节点个数
     */
    private int size;

    /**
     * 获取数组的实际元素个数
     *
     * @return 数组的实际元素个数
     */
    public int size() {
        return this.size;
    }

    /**
     * 获取数组的长度
     *
     * @return 数组的长度
     */
    public int length() {
        return this.maxSize;
    }

    /**
     * 最小堆的构造函数
     *
     * @param arr 数组
     */
    public MinHeap(Integer[] arr) {
        buildMinHeap(arr);
    }

    /**
     * 构建最小堆
     *
     * @param arr 数组
     */
    private void buildMinHeap(Integer[] arr) {
        this.size = arr.length;
        this.maxSize = arr.length;
        this.array = arr;
        // 获取最后一个节点的下标
        int lastIndex = arr.length - 1;
        // 从最后一个非叶子节点开始进行下沉
        for (int i = getParentIndex(lastIndex); i >= 0; i--) {
            downAdjust(i);
        }
    }

    /**
     * 在堆的末尾插入一个数据
     *
     * @param data 数值
     */
    public void insert(int data) {
        if (size >= maxSize) {
            resize();
        }
        this.array[this.size++] = data;
        upAdjust();
    }

    /**
     * 数组扩容操作
     */
    private void resize() {
        // 新数组的长度为原数组的2倍
        this.maxSize = this.maxSize * 2;
        // 初始化新数组
        Integer[] newArray = new Integer[maxSize];
        // 将原数组的元素复制到新数组中
        System.arraycopy(this.array, 0, newArray, 0, this.size);
        // 使用新数组替换原数组
        this.array = newArray;
    }

    /**
     * 上浮操作
     */
    private void upAdjust() {
        // 数组最后一个节点所在的下标，即需要上浮的节点
        int currentIndex = this.size - 1;
        int parentIndex = getParentIndex(currentIndex);
        // 将当前孩子节点使用临时变量保存
        int temp = this.array[currentIndex];
        // 如果当前孩子节点的下标大于0，并且当前孩子节点的值小于父节点的值
        while (currentIndex > 0 && temp < this.array[parentIndex]) {
            // 将父节点的值和当前孩子节点的值进行交换
            this.array[currentIndex] = this.array[parentIndex];
            // 将当前孩子节点的值修改为之前的父节点的值
            currentIndex = parentIndex;
            // 维护父节点的下标
            parentIndex = getParentIndex(currentIndex);
        }
        this.array[currentIndex] = temp;
    }

    /**
     * 移除堆顶的元素
     *
     * @return 堆顶的元素
     */
    public Integer remove() {
        if (this.size == 0) {
            return null;
        }
        Integer removeData = this.array[0];
        // 获取最后一个节点
        this.array[0] = this.array[size - 1];
        downAdjust(0);
        this.array[--size] = null;
        return removeData;
    }

    /**
     * 下沉操作
     *
     * @param parentIndex 需要下沉的节点下标
     */
    private void downAdjust(int parentIndex) {
        // 获取左孩子节点的下标
        int childIndex = getLeftChildIndex(parentIndex);
        // 将需要下沉的节点使用临时变量保存
        int temp = this.array[parentIndex];
        // 如果左孩子节点的下标还在堆的有效个数之内，
        while (childIndex < this.size) {
            // 右孩子节点为左孩子节点的下一位
            int rightChildIndex = childIndex + 1;
            // 如果有右孩子节点，并右孩子节点比左孩子节点的值小，则定位到右孩子节点
            if (rightChildIndex < this.size && this.array[rightChildIndex] < this.array[childIndex]) {
                childIndex++;
            }
            // 如果需要下沉的节点小于孩子节点中最小的那个节点的值，直接打断程序，不继续下沉
            if (temp <= this.array[childIndex]) {
                break;
            }
            // 调换父子节点的值
            this.array[parentIndex] = this.array[childIndex];
            // 将父节点的下标修改为子节点的下标
            parentIndex = childIndex;
            // 维护左孩子节点的下标
            childIndex = getLeftChildIndex(parentIndex);
        }
        this.array[parentIndex] = temp;
    }

    /**
     * 通过孩子节点下标，获取父节点下标
     *
     * @param childIndex 孩子节点下标
     * @return 父节点下标
     */
    private int getParentIndex(int childIndex) {
        // 通过取余数的方式，直接获取左右孩子节点的父节点
        return (childIndex - 1) / 2;
    }

    /**
     * 通过父节点下标，获取左孩子节点下标
     *
     * @param parentIndex 父节点下标
     * @return 左孩子节点下标
     */
    private int getLeftChildIndex(int parentIndex) {
        return 2 * parentIndex + 1;
    }

    /**
     * 通过父节点下标，获取右孩子节点下标
     *
     * @param parentIndex 父节点下标
     * @return 右孩子节点下标
     */
    private int getRightChildIndex(int parentIndex) {
        return 2 * parentIndex + 2;
    }

}

最后

本文Github https://github.com/herenpeng/code-learn 已收录，欢迎Star。

坚持原创技术分享，您的支持将鼓励我继续创作！
-------------这是我的底线^_^-------------