数据结构之堆与优先队列

清疚 2022-01-30 09:39 343阅读 0赞

堆与优先队列：

## 堆 ##

堆必须是一个完全二叉树。除了最后一层，其他层的节点个数都是满的，最后一层的节点都靠左排列

堆中的每个节点的值必须大于等于（或者小于等于）其子树中每个节点的值或者说堆中每个节点的值都大于等于（或者小于等于）其左右子节点的值。这两种表述是等价的。

对于每个节点的值都大于等于子树中每个节点值的堆，我们叫作“大顶堆”。对于每个节点的值都小于等于子树中每个节点值的堆，我们叫作“小顶堆”。

![20190510214135.png][]

在图中1和2是大顶堆,3是小顶堆,4不是堆（最后一层不是右子节点）。

## 实现 ##

完全二叉树比较适合用数组来存储。用数组来存储完全二叉树是非常节省存储空间的。因为我们不需要存储左右子节点的指针，单纯地通过数组的下标，就可以找到一个节点的左右子节点和父节点。

![20190510214714.png][]

数组中下标为 i 的节点的左子节点，就是下标为 $i$的节点，右子节点就是下标为$i\*2+1$的节点，父节点就是下标为 的节点。

## 堆化 ##

新插入的元素放到堆的最后,我们需要进行调整，让其重新满足堆的特性，这个过程就叫作堆化（heapify）。 堆化实际上有两种，从下往上和从上往下。

![20190510215315.png][]

新插入的节点与父节点对比大小。如果不满足子节点小于等于父节点的大小关系，就互换两个节点。重复这个过程，直到父子节点之间满足刚说的那种大小关系。

![20190510215720.png][]

删除堆顶元素

堆顶元素存储的其实是堆中数据中的最大值或者最小值。 如果我们构造的是大顶堆，堆顶元素就是最大的元素。当我们删除堆顶元素之后，就需要把第二大的元素放到堆顶，那第二大元素肯定会出现在左右子节点中。然后我们再迭代地删除第二大节点，以此类推，直到叶子节点被删除。

![img][]

## 代码 ##

复用原先的Array代码并且加以改造

<table> 
 <tbody> 
 <tr> 
 <td><pre>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 </pre></td> 
 <td><pre>public class Array&lt;E&gt; {
 private E[] data; private int size; // 构造函数，传入数组的容量capacity构造Array public Array(int capacity){
 data = (E[])new Object[capacity]; size = 0; } // 无参数的构造函数，默认数组的容量capacity=10 public Array(){
 this(10); } public Array(E[] arr){
 data = (E[])new Object[arr.length]; for(int i = 0 ; i &lt; arr.length ; i ++) data[i] = arr[i]; size = arr.length; } // 获取数组的容量 public int getCapacity(){
 return data.length; } // 获取数组中的元素个数 public int getSize(){
 return size; } // 返回数组是否为空 public boolean isEmpty(){
 return size == 0; } // 在index索引的位置插入一个新元素e public void add(int index, E e){
 if(index &lt; 0 || index &gt; size) throw new IllegalArgumentException("Add failed. Require index &gt;= 0 and index &lt;= size."); if(size == data.length) resize(2 * data.length); for(int i = size - 1; i &gt;= index ; i --) data[i + 1] = data[i]; data[index] = e; size ++; } // 向所有元素后添加一个新元素 public void addLast(E e){
 add(size, e); } // 在所有元素前添加一个新元素 public void addFirst(E e){
 add(0, e); } // 获取index索引位置的元素 public E get(int index){
 if(index &lt; 0 || index &gt;= size) throw new IllegalArgumentException("Get failed. Index is illegal."); return data[index]; } // 修改index索引位置的元素为e public void set(int index, E e){
 if(index &lt; 0 || index &gt;= size) throw new IllegalArgumentException("Set failed. Index is illegal."); data[index] = e; } // 查找数组中是否有元素e public boolean contains(E e){
 for(int i = 0 ; i &lt; size ; i ++){
 if(data[i].equals(e)) return true; } return false; } // 查找数组中元素e所在的索引，如果不存在元素e，则返回-1 public int find(E e){
 for(int i = 0 ; i &lt; size ; i ++){
 if(data[i].equals(e)) return i; } return -1; } // 从数组中删除index位置的元素, 返回删除的元素 public E remove(int index){
 if(index &lt; 0 || index &gt;= size) throw new IllegalArgumentException("Remove failed. Index is illegal."); E ret = data[index]; for(int i = index + 1 ; i &lt; size ; i ++) data[i - 1] = data[i]; size --; data[size] = null; // loitering objects != memory leak if(size == data.length / 4 &amp;&amp; data.length / 2 != 0) resize(data.length / 2); return ret; } // 从数组中删除第一个元素, 返回删除的元素 public E removeFirst(){
 return remove(0); } // 从数组中删除最后一个元素, 返回删除的元素 public E removeLast(){
 return remove(size - 1); } // 从数组中删除元素e public void removeElement(E e){
 int index = find(e); if(index != -1) remove(index); } public void swap(int i, int j){
 if(i &lt; 0 || i &gt;= size || j &lt; 0 || j &gt;= size) throw new IllegalArgumentException("Index is illegal."); E t = data[i]; data[i] = data[j]; data[j] = t; } @Override public String toString(){
 StringBuilder res = new StringBuilder(); res.append(String.format("Array: size = %d , capacity = %d\n", size, data.length)); res.append('['); for(int i = 0 ; i &lt; size ; i ++){
 res.append(data[i]); if(i != size - 1) res.append(", "); } res.append(']'); return res.toString(); } // 将数组空间的容量变成newCapacity大小 private void resize(int newCapacity){
 E[] newData = (E[])new Object[newCapacity]; for(int i = 0 ; i &lt; size ; i ++) newData[i] = data[i]; data = newData; } } </pre></td> 
 </tr> 
 </tbody> 
</table>

![20190510220210.png][]

![20190510220241.png][]

## 优先队列 ##

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

![20190510222335.png][]

## 参考资料 ##

《大话数据结构》

《数据结构与算法之美》

《玩转数据结构》

[20190510214135.png]: /images/20220130/ad75a4e3a89e49ca8623147394d81385.png
[20190510214714.png]: /images/20220130/40dc2a086532440c86c30d40f78de9e7.png
[20190510215315.png]: /images/20220130/401ebd44ae0042dea2c40b36686b6473.png
[20190510215720.png]: /images/20220130/8d1c355b16e3462698d0e6ec7976ed7d.png
[img]: /images/20220130/0372305c4f164be3b6719e7c5da3a165.png
[20190510220210.png]: /images/20220130/47693635365f4fdfb63db06ca097c1c5.png
[20190510220241.png]: /images/20220130/a3dae23ea2fe40e18ccd3f374cdb811f.png
[20190510222335.png]: /images/20220130/e1c7f8918cc74e6a805dffebb98712c8.png