Fork me on GitHub

堆树详解及使用最大堆实现优先队列

发表于 | 分类于 |
本文共计: 3,990 | 阅读耗时 ≈ 21

堆树详解及使用最大堆实现优先队列

定义

堆树的定义如下：

  1. 堆树是一颗完全二叉树；

  2. 堆树中某个节点的值总是不大于或不小于其孩子节点的值；

  3. 堆树中每个节点的子树都是堆树。

当父节点的键值总是大于或等于任何一个子节点的键值时为最大堆。 当父节点的键值总是小于或等于任何一个子节点的键值时为最小堆。

构造二叉堆

这里是一自定义的动态数组作为底层来实现最大堆这种数据结构，使用数组存储二叉堆具有如下性质，如下如所示：

11

就是通过其中的任何一个节点可以找到其父节点或者是左孩子和右孩子节点。

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
public class MaxHeap<E extends Comparable<E>> {
    private Array<E> data;

    /**
     * 最大堆初始化
     * @param capacity
     */
    public MaxHeap(int capacity){
        data = new Array<>(capacity);
    }
    
    /**
     * f返回某一节点的父节点
     * @param index node
     * @return
     */
    private int parent(int index){
        if (index == 0 || index > data.getSize()){
            throw  new IllegalArgumentException("index has no parent node");
        }
        return (index-1)/2;
    }

    /**
     * 返回当前节点的左孩子节点
     * @param index node
     * @return
     */
    public int leftChild(int index){
        if (index == 0 || index > data.getSize()){
            throw  new IllegalArgumentException("index has no parent node");
        }
        return index * 2 + 1;
    }

    /**
     * 返回当前节点的右孩子节点
     * @param index
     * @return
     */
    public int rightChild(int index){
        if (index == 0 || index > data.getSize()){
            throw  new IllegalArgumentException("index has no parent node");
        }
        return index * 2 + 2;
    }

关于判断堆的大小及是否为空都是很简单的操作。就不在这里多说了。下面说一下最大堆中的sift up,sift down和heapify操作。

向堆中添加元素及sift up

对于下面的一个堆，插入元素52时，因为我们使用的是数组存储的二叉堆，然后插入的元素需要满足二叉堆的性质，如果直接通过遍历数组来找到其位置，复杂度是O(n)的，这里采用的是sift up也就是先将元素插入堆的末尾，然后通过上浮操作来找到其位置，复杂度是O(logn)的。

12

sift up具体实现如下图：

1

具体的实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
**
* 添加元素
* @param e
*/
public void add(E e){
    data.addLast(e);
    siftUp(data.getSize()-1);
}

/**
* 从节点index开始元素上浮
* @param index
*/
public void siftUp(int index){
    while (index > 0 && data.get(parent(index)).compareTo(data.get(index)) < 0 ){
        data.swap(index, parent(index));
        index = parent(index);
    }
}

取出堆中最大元素及sift down

通过性质我们可以知道对于一个最大堆来说，堆中最大的元素在堆顶。取出堆顶的元素之后谁去堆顶？这里采取的操作时将堆顶的62元素和堆底的16交换然后删除16，再将16下沉，找到其合适的位置。这样的复杂度只有O(logn).

13

sift down 具体的实现如下：

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
/**
     * 取出堆中的最大元素
     * @return
     */
    public E extractMax(){
        E ret = findMax();
        data.swap(0, data.getSize()- 1);
        data.deleteLast();
        siftDown(0);
        return ret;
    }

    /**
     * 元素下沉操作
     * @param index
     */
    public void siftDown(int index){
        while (leftChild(index) <  data.getSize()){
            if (rightChild(index) < data.getSize() && data.get(leftChild(index)).compareTo(data.get(rightChild(index))) < 0){
                if (data.get(index).compareTo(data.get(rightChild(index))) < 0){
                    data.swap(index, rightChild(index));
                    index = rightChild(index);
                }
            }
            if (data.get(index).compareTo(data.get(leftChild(index))) > 0){
                break;
            }
            data.swap(index, leftChild(index));
            index = leftChild(index);
        }
    }

    /**
     *   取出堆中的最大元素，并且替换成元素e
     * @param e 元素
     * @return
     */
    public E replace(E e){

        E ret = findMax();
        data.set(0, e);
        siftDown(0);
        return ret;
    }

将任意数组整理成最大堆和heapify

一般随便一个数组是不符合最大堆的性质的，如何将一个数组整理成最大堆呢？寻常的想法是将数组中的n个元素不断的插入空堆中，这样操作的复杂度是O(nlogn)的，这里采用heapify的操作来实现，其实就是将不是叶子结点的元素全部采用下沉操作，找到自己的位置，时间复杂度为O(n)的。

heapify的操作具体如下：

3

具体的代码实现如下：

首先是数组的初始化

1
2
3
4
5
6
public Array(E[] arr){
    data = (E[])new Object[arr.length];
    for(int i = 0 ; i < arr.length ; i ++)
        data[i] = arr[i];
    size = arr.length;
}

然后是最大堆中的实现：

1
2
3
4
5
6
7
8
9
10
11
/**
* heapify 操作
* @param arr
*/
public MaxHeap(E[] arr){
    data = new Array<>(arr);
    int index= parent(arr.length-1);
    for (int i = 0; i < index ; i++){
        siftDown(index);
    }
}

替换堆中的任意元素

是实现的方法比较简单，就是将堆中的最大元素由替换元素替换，然后进行下沉操作，O(logn)的时间复杂度

1
2
3
4
5
6
7
8
9
10
11
12
 /**
 *   取出堆中的最大元素，并且替换成元素e
 * @param e 元素
 * @return
 */
public E replace(E e){

    E ret = findMax();
    data.set(0, e);
    siftDown(0);
    return ret;
}

完整代码

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
package heap;

import arrary.Array;

/**
 * 最大堆
 * @author WilsonSong
 * @date 2018/6/11
 */
public class MaxHeap<E extends Comparable<E>> {
    private Array<E> data;

    /**
     * 最大堆初始化
     * @param capacity
     */
    public MaxHeap(int capacity){
        data = new Array<>(capacity);
    }

    /**
     * heapify 操作
     * @param arr
     */
    public MaxHeap(E[] arr){
        data = new Array<>(arr);
        int index= parent(arr.length-1);
        for (int i = 0; i < index ; i++){
            siftDown(index);
        }
    }

    public MaxHeap(){
        data = new Array<>();
    }

    /**
     * size
     * @return
     */
    public int getSize(){
        return data.getSize();
    }

    /**
     * 是否为空
     * @return
     */
    public boolean isEmpty(){
        return data.isEmpty();
    }

    /**
     * f返回某一节点的父节点
     * @param index node
     * @return
     */
    private int parent(int index){
        if (index == 0 || index > data.getSize()){
            throw  new IllegalArgumentException("index has no parent node");
        }
        return (index-1)/2;
    }

    /**
     * 返回当前节点的左孩子节点
     * @param index node
     * @return
     */
    public int leftChild(int index){
        if (index == 0 || index > data.getSize()){
            throw  new IllegalArgumentException("index has no parent node");
        }
        return index * 2 + 1;
    }

    /**
     * 返回当前节点的右孩子节点
     * @param index
     * @return
     */
    public int rightChild(int index){
        if (index == 0 || index > data.getSize()){
            throw  new IllegalArgumentException("index has no parent node");
        }
        return index * 2 + 2;
    }

    /**
     * 添加元素
     * @param e
     */
    public void add(E e){
        data.addLast(e);
        siftUp(data.getSize()-1);
    }

    /**
     * 从节点index开始元素上浮
     * @param index
     */
    public void siftUp(int index){
        while (index > 0 && data.get(parent(index)).compareTo(data.get(index)) < 0 ){
            data.swap(index, parent(index));
            index = parent(index);
        }
    }

    /**
     * 最大堆中的元素
     * @return
     */
    public E findMax(){
        if (data.getSize() == 0){
            throw new IllegalArgumentException("This Heap has no elements");
        }
        return data.get(0);
    }

    /**
     * 取出堆中的最大元素
     * @return
     */
    public E extractMax(){
        E ret = findMax();
        data.swap(0, data.getSize()- 1);
        data.deleteLast();
        siftDown(0);
        return ret;
    }

    /**
     * 元素下沉操作
     * @param index
     */
    public void siftDown(int index){
        while (leftChild(index) <  data.getSize()){
            if (rightChild(index) < data.getSize() && data.get(leftChild(index)).compareTo(data.get(rightChild(index))) < 0){
                if (data.get(index).compareTo(data.get(rightChild(index))) < 0){
                    data.swap(index, rightChild(index));
                    index = rightChild(index);
                }
            }
            if (data.get(index).compareTo(data.get(leftChild(index))) > 0){
                break;
            }
            data.swap(index, leftChild(index));
            index = leftChild(index);
        }
    }

    /**
     *   取出堆中的最大元素，并且替换成元素e
     * @param e 元素
     * @return
     */
    public E replace(E e){

        E ret = findMax();
        data.set(0, e);
        siftDown(0);
        return ret;
    }

}

作为底层的数组的实现如下：

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
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
package arrary;

/**
 * 数组
 * @author WilsonSong
 * @date 2018/5/28
 */
public class Array<E> {

    private  E[] data;
    private int size;

    /**
     * 构造函数，传入数组容量capacity
     * @param capacity 数组容量
     */
    public Array(int capacity){
        data = (E[])new Object[capacity];
        size = 0;
    }

    /**
     * 无参数的构造函数，默认数组容量为10
     */
    public Array(){
        this(10);
    }

    /**
     * 构造函数
     * @param arr
     */
    public Array(E[] arr){
        data = (E[])new Object[arr.length];
        for(int i = 0 ; i < arr.length ; i ++)
            data[i] = arr[i];
        size = arr.length;
    }

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

    /**
     * 获取数组的容量
     * @return
     */
    public int getCapacity(){
        return data.length;
    }

    /**
     * 判断数组是否为空
     * @return
     */
    public boolean isEmpty(){
        return size == 0;
    }


    /**
     * 交换数组中的任意两个元素
     * @param i
     * @param j
     */
    public void swap(int i, int j){
        if (i < 0 || j < 0 || i > size || j > size ){
            throw new IllegalArgumentException("i or j do not in this array");
        }
        E ret = data[i];
        data[i] = data[j];
        data[j] = ret;

    }
    /**
     * 向数组中指定位置插入元素
     * @param index 插入位置
     * @param e 插入表元素
     */
    public void add(int index, E e){
        if(size == data.length){
            resize(2*data.length);
        }
        if (index < 0 || index > size){
            throw new IllegalArgumentException("Add failed. Required index >= 0 & index <= size ");
        }
        for (int i =  size -1; i >= index; i--){
            data[i+1] = data[i];
        }
        data[index] = e;
        size ++ ;
    }

    /**
     * 向数组的末尾插入元素
     * @param e 元素
     */
    public void addLast(E e){
        add(size, e);
    }

    /**
     *向数组第一个位置插入元素
     * @param e 元素
     */
    public void addFirst(E e){
        add(0,e);
    }

    /**
     * 查询指定位置元素
     * @param index
     * @return
     */
    public E get(int index){
        if ( index < 0||index > size){
            throw new IllegalArgumentException("Get failed. Index is illegal.");
        }
        return data[index];
    }

    public E getLast(){
        return get(size -1);
    }

    public E getFirst(){
        return get(0);
    }
    /**
     * 重设指定位置元素
     * @param index
     * @return
     */
    public void set(int index, E e){
        if ( index < 0||index > size){
            throw new IllegalArgumentException("Set failed. Index is illegal.");
        }
        data[index] = e;
    }

    /**
     * 查询是否包含某个元素
     * @param e 查询的元素
     * @return
     */
    public boolean contains(E e){
        for (int i =0; i<size; i++){
            if (data[i].equals(e)){
                return true;
            }
        }
        return false;
    }

    /**
     * 查询某个元素的位置，如果不存在元素e，则返回-1
     * @param e 元素
     * @return
     */
    public int find(E e){
        for (int i = 0; i< size; i++){
            if (data [i].equals(e)){
                return i;
            }
        }
        return -1;
    }

    /**
     * 删除索引位置的元素
     * @param index 索引
     * @return
     */
    public E delete(int index){
        if (index < 0 ||  index > size){
            throw new IllegalArgumentException("Delete failed. Index is illegal.");
        }
        E ret = data[index];
        for (int i = index +1 ; i< size; i++){
            data[i-1] = data[i];
        }
        size--;
        data[size] = null;
        if (size == data.length / 2){
            resize(data.length/2);
        }
        return ret;
    }

    /**
     * 删除第一个位置元素
     * @return
     */
    public E deleteFirst(){
        return delete(0);
    }
    /**
     * 删除最后一个位置元素
     * @return
     */
    public E deleteLast(){
         return delete(size -1);
    }

    /**
     * 删除元素
     * @param e 元素
     * @return
     */
    public void deleteElement(E e){
        int index = find(e);
        if (index != -1){
            delete(index);
        }else {
            throw new IllegalArgumentException("Delete failed. Element is not exist");
        }
    }

    @Override
    public String toString(){
        StringBuilder res = new StringBuilder();
        res.append(String.format("Array: size = %d, capacity = %d.\n",size,getCapacity() ));
        res.append("[");
        for (int i = 0; i < size; i++){
            res.append(data[i]);
            if (i != size -1){
                res.append(",");
            }
        }
        res.append("]");
        return res.toString();
    }

    /**
     * 数组扩容
     * @param newCapacity 数组容量
     */
    private void resize(int newCapacity){
        E[] newData = (E[]) new Object[newCapacity];
        for (int i = 0; i < size; i++){
            newData[i] =data[i];
        }
        data = newData;
    }

}

基于最大堆实现优先队列

普通的队列是一种先进先出的数据结构，元素在队列尾追加，而从队列头删除。在优先队列中，元素被赋予优先级。当访问元素时，具有最高优先级的元素最先删除。优先队列具有最高级先出 （first in, largest out）的行为特征。优先队列有很多的实现方式，但通常采用堆数据结构来实现。因为这两者很像。

具体的实现如下：

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
package heap;

import queue.Queue;

/**
 * 优先队列
 * @author WilsonSong
 * @date 2018/6/11
 */
public class PriorityQueue<E extends Comparable<E>> implements Queue<E> {

    private MaxHeap<E> maxHeap;
    public PriorityQueue(){
        maxHeap = new MaxHeap<>();
    }

    @Override
    public int getSize(){
        return maxHeap.getSize();
    }

    @Override
    public boolean isEmpty(){
        return maxHeap.isEmpty();
    }

    @Override
    public E getFront(){
        return maxHeap.findMax();
    }

    @Override
    public void enqueue(E e){
        maxHeap.add(e);
    }

    @Override
    public E dequeue(){
        return maxHeap.extractMax();
    }
}

应用统计前k个出现频次高的数字

Given a non-empty array of integers, return the k most frequent elements.

Example 1:

1
2
Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]

Example 2:

1
2
Input: nums = [1], k = 1
Output: [1]

Note:

  • You may assume k is always valid, 1 ≤ k ≤ number of unique elements.
  • Your algorithm’s time complexity must be better than O(n log n), where n is the array’s size

使用优先队列来解决这么问题比较方便，将前k个频次最高的元素放入队列，优先级高的元素出现的频次是这k个中最小的，然后只要有出现频次比他高的就可以替换掉。

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
package heap;

import java.util.*;
import java.util.PriorityQueue;

/**
 * Given a non-empty array of integers, return the k most frequent elements.

 Example 1:

 Input: nums = [1,1,1,2,2,3], k = 2
 Output: [1,2]
 Example 2:

 Input: nums = [1], k = 1
 Output: [1]
 Note:

 You may assume k is always valid, 1 ≤ k ≤ number of unique elements.
 Your algorithm's time complexity must be better than O(n log n), where n is the array's size.
 * @author WilsonSong
 * @date 2018/6/11
 */
public class heapSolution2 {
    public static List<Integer> topKFrequent(int[] nums, int k) {

        /**
         * 定义一个频次的私有类
         */
        class Freq implements Comparable<Freq>{
            public int e;
            public int freq;

            public Freq(int e, int freq){
                this.e = e;
                this.freq = freq;
            }

            @Override
            public int compareTo(Freq anotherFreq){
                if (this.freq < anotherFreq.freq) {
                    return -1;
                }
                else if (this.freq > anotherFreq.freq){
                    return 1;
                }
                else{
                    return 0;
                }
            }
        }

        Map<Integer, Integer> map = new HashMap<>();
        for (int num : nums){
            if (!map.containsKey(num)){
                map.put(num,1);
            }else {
                map.put(num, map.get(num) + 1);
            }
        }

        PriorityQueue<Freq> priorityQueue = new PriorityQueue<>();  //按照优先级排列，出现频次低的优先级高
        for (int key : map.keySet()){
            if (priorityQueue.size() < k){
                priorityQueue.add(new Freq(key, map.get(key)));
            }else {
                if (map.get(key) > priorityQueue.peek().freq){
                    priorityQueue.remove();
                    priorityQueue.add(new Freq(key, map.get(key)));
                }
            }

        }
        List list = new ArrayList();
        while (!priorityQueue.isEmpty()){
            list.add(priorityQueue.poll().e);
        }
        return list;
    }

    public static void main(String[]  args){
        int[] array = {1,2,2,3,3,3};
        List<Integer> list = topKFrequent(array,2);
        System.out.println(list.toString());
    }
}

然后觉得太复杂了，然后又改了改，就是存入hashmap之后，因为其出现的频次对应的是value的值，然后让hashmap根据value排序，然后输出即可。

hashmap根据value排序需要先将其视图存入list中，然后使用collections的排序方法来做，实现一个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
package heap;

import java.util.*;

/**
 * Given a non-empty array of integers, return the k most frequent elements.

 Example 1:

 Input: nums = [1,1,1,2,2,3], k = 2
 Output: [1,2]
 Example 2:

 Input: nums = [1], k = 1
 Output: [1]
 Note:

 You may assume k is always valid, 1 ≤ k ≤ number of unique elements.
 Your algorithm's time complexity must be better than O(n log n), where n is the array's size.
 * @author WilsonSong
 * @date 2018/6/11
 */
public class heapSolution {

        public static   List<Integer> topKFrequent(int[] nums, int k) {
            List<Integer> list = new ArrayList<>();
            Map<Integer, Integer> map = new HashMap<>();
            for (int num : nums){
                if (!map.containsKey(num)){
                    map.put(num,1);
                }
                map.put(num, map.get(num)+1);
            }

            List<Map.Entry<Integer,Integer>> list1 = new ArrayList<>();
            list1.addAll(map.entrySet());
            Collections.sort(list1, new Comparator<Map.Entry<Integer, Integer>>() {
                @Override
                public int compare(Map.Entry<Integer, Integer> o1, Map.Entry<Integer, Integer> o2) {
                    return o2.getValue().compareTo( o1.getValue());
                }
            });
            for (Map.Entry<Integer, Integer> mapping : list1){
                if (list.size() >= k){
                    break;
                }
                list.add(mapping.getKey());
            }
            return list;
    }

    public static void main(String[]  args){
            int[] array = {2,2,2,3,3,5,5,5,4,5,4,4,4,4,5};
        List<Integer> list = topKFrequent(array,2);
        System.out.println(list.toString());

   }
}

本文标题:堆树详解及使用最大堆实现优先队列

文章作者:WilsonSong

发布时间:2018年06月12日 - 11:06

最后更新:2018年08月27日 - 21:08

原始链接:https://songwell1024.github.io/2018/06/12/MaxHeapAndPriorityQueue/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

-------------本文结束感谢您的阅读-------------