Posts 数据结构--堆
Post
Cancel

数据结构--堆

堆(Heap)是一棵完全二叉树,没有使用父指针和子指针,使用数组描述。

完全二叉树的特点:按照从上到下,从左向右的顺序填充,当前层没有填满时不允许填下一层。

堆的属性

堆分为大根堆(最大堆)和小根堆(最小堆)。

  • 在大根堆中,父节点的值比每一个子节点的值都要大。
  • 在小根堆中,父节点的值比每一个子节点都要小。

大根堆的根节点永远是最大值,小根堆的根节点永远是最小值。

堆的存储结构

将以下数组存放在堆中

1
[7, 6, 5, 2, 3]

节点在数组中的位置 i 与它的父子节点之间存在一个映射关系:

1
2
3
parent(i) = floor((i - 1) / 2)
left(i) = 2i + 1
right(i) = 2i + 2

一个节点的父节点等于它的索引减去 1 除 2 向下取整。左右节点的索引总是相邻。

节点索引父节点索引左子节点索引右子节点索引
70-112
71034
52056
23178
341910

根节点 7 没有父节点,它的父节点索引是 -1,节点 5、2、3 没有子节点,它们的子节点索引超过了数组的最大索引。在使用时要判断索引是否是有效值。

堆的操作

两个原子操作保证在插入和删除节点维持堆的属性:

  • shiftUp() : 如果一个节点比它的父节点大(大根堆)或小(小根堆),需要将这个节点与父节点交换位置。
  • shiftDown() :如果一个节点比它的子节点小(大根堆)或大(小根堆),需要将这个节点与(左或者右)子节点交换位置。

以上两个操作是一个递归的过程,时间复杂度 O(log N) 。基于这两个原子操作还有一些其他的操作:

  • insert(value) :在堆的尾部插入一个节点,然后使用 shiftUp() 来修复堆属性。
  • remove() :删除并返回堆顶节点。将最后一个节点放被删除节点的位置,然后使用 shiftDown() 来修复堆属性。
  • removeAt(index) :删除堆中的任意节点。将被删除节点与最后一个节点交换位置,交换后如果当前节点比父节点大(小),使用 shiftUp() 修复堆属性,如果它比子节点小(大),使用 shiftDown() 修复堆属性。

以上所有的操作时间复杂度都是 O(log N) 。

堆的可以通过反复调用 insert(value) 来建立。

堆的 Java 实现

这里使用了泛型和函数式接口,根据指定的 Comparator 来构造堆。

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
package top.cloudli.heap;

import java.util.Arrays;
import java.util.Comparator;

/**
 * 堆(Heap)
 * 根据 {@link Comparator} 构造最大(小)堆
 *
 * @author Cloud Li
 */
@SuppressWarnings("unchecked")
public class Heap<T> {
    private Object[] heap;
    private int length = 0;

    private Comparator<T> cmp= Comparator.comparingInt(Object::hashCode);

    public Heap(T[] array) {
        this(array, null);
    }

    public Heap(T[] array, Comparator<T> cmp) {
        heap = new Object[array.length];
        if (cmp != null)
            this.cmp = cmp;
        build(array);
    }

    /**
     * 构造堆
     *
     * @param array 用来构造堆的元素
     */
    private void build(T[] array) {
        for (T e : array) {
            insert(e);
        }
    }

    /**
     * 插入一个元素
     *
     * @param e 被插入的元素
     */
    public void insert(T e) {
        if (length == heap.length)
            resize();
        heap[length] = e;
        shiftUp(length);
        length++;
    }

    public T peek() {
        return (T) heap[0];
    }

    /**
     * 移除并返回根节点
     *
     * @return 根节点元素
     */
    public T remove() {
        T t = (T) heap[0];

        heap[0] = heap[length - 1];
        length--;
        shiftDown(0);

        return t;
    }

    /**
     * 删除指定位置的元素
     *
     * @param i 目标元素索引,起始为 0
     * @return 被删除的元素
     */
    public T removeAt(int i) {
        if (i < 0 || i >= length)
            throw new ArrayIndexOutOfBoundsException(i);

        T t = (T) heap[i];

        swap(i, length - 1);
        length--;

        if (cmp.compare((T) heap[i], (T) heap[parent(i)]) > 0) {
            shiftUp(i);
        } else {
            shiftDown(i);
        }

        return t;
    }

    /**
     * 扩容
     */
    private void resize() {
        Object[] old = heap;
        Object[] t = new Object[old.length << 1];
        System.arraycopy(old, 0, t, 0, old.length);
        heap = t;
    }

    /**
     * 获取当前元素的父节点索引
     *
     * @param i 当前元素的索引
     * @return 父节点索引 floor(i - 1 / 2)
     */
    private int parent(int i) {
        return (i - 1) >> 1;
    }

    /**
     * 获取当前元素左节点的索引
     *
     * @param i 当前元素的索引
     * @return 左节点的索引 2i + 1
     */
    private int left(int i) {
        return (i << 1) + 1;
    }

    /**
     * 获取当前元素右节点的索引
     *
     * @param i 当前元素的索引
     * @return 右节点的索引 2i + 2
     */
    private int right(int i) {
        return (i << 1) + 2;
    }

    /**
     * 上移
     *
     * @param i 当前元素的索引
     */
    private void shiftUp(int i) {
        int parent = parent(i);

        if (parent < 0)
            return;

        // 如果当前元素比它的父节点大(小),交换位置
        if (cmp.compare((T) heap[i], (T) heap[parent]) > 0) {
            swap(i, parent);
            shiftUp(parent);
        }
    }

    /**
     * 下移
     *
     * @param i 当前元素的索引
     */
    private void shiftDown(int i) {
        int left = left(i), right = right(i), child;

        if (left >= length || right >= length)
            return;

        // 如果当前元素比它的子节点小(大),交换位置
        if (cmp.compare((T) heap[left], (T) heap[i]) > 0) {
            child = left;
        } else if (cmp.compare((T) heap[right], (T) heap[i]) > 0) {
            child = right;
        } else {
            child = -1;
        }

        if (child != -1) {
            swap(i, child);
            shiftDown(child);
        }
    }

    /**
     * 交换元素
     *
     * @param i 索引
     * @param j 索引
     */
    private void swap(int i, int j) {
        Object t = heap[i];
        heap[i] = heap[j];
        heap[j] = t;
    }

    public int size() {
        return length;
    }

    public int maxSize() {
        return heap.length;
    }

    @Override
    public String toString() {
        Object[] t = new Object[length];
        System.arraycopy(heap, 0, t, 0, length);
        return Arrays.toString(t);
    }
}
1
2
3
4
5
6
7
8
9
10
11
public class Main {

    public static void main(String[] args) {
        Integer[] arr = {5, 2, 7, 3, 6};

        // 构造一个大根堆
        Heap<Integer> heap = new Heap<>(arr, Integer::compareTo);

        out.printf("Size: %d, MaxSize: %d, nodes: %s\n", heap.size(), heap.maxSize(), heap.toString());
    }
}

运行结果:

1
2
3
4
Size: 5, MaxSize: 5, nodes: [7, 6, 5, 2, 3]

Process finished with exit code 0

如果要构造小根堆:

1
Heap<Integer> heap = new Heap<>(arr, Comparator.reverseOrder());

如果要使用自定义对象,可以传入一个 lambda 表达式,指定比较规则。

OLDER POST NEWER POST

Comments powered by Disqus.

内容

Search Results