一淮野、堆
堆（英語：heap)是計算機科學中一類特殊的數(shù)據(jù)結(jié)構(gòu)的統(tǒng)稱鸵鸥。堆通常是一個可以被看做一棵樹的數(shù)組對象圃泡。堆總是滿足下列性質(zhì)：
- 堆中某個節(jié)點的值總是不大于或不小于其父節(jié)點的值后添；
- 堆總是一棵完全二叉樹愤钾。
堆的實現(xiàn)通過構(gòu)造二叉堆（binary heap），實為二叉樹的一種灾锯；由于其應(yīng)用的普遍性兢榨，當不加限定時，均指該數(shù)據(jù)結(jié)構(gòu)的這種實現(xiàn)顺饮。這種數(shù)據(jù)結(jié)構(gòu)具有以下性質(zhì)。
- 任意節(jié)點小于（或大于）它的所有后裔凌那，最小元（或最大元）在堆的根上（堆序性）兼雄。
- 堆總是一棵完全樹。即除了最底層帽蝶，其他層的節(jié)點都被元素填滿赦肋，且最底層盡可能地從左到右填入。
將根節(jié)點最大的堆叫做最大堆或大根堆，根節(jié)點最小的堆叫做最小堆或小根堆佃乘。
我們這里講的是二叉堆囱井。
堆的入隊和出隊的時間復(fù)雜度都是O(log n)
上圖就是一個最大堆的事例
下面我們使用數(shù)組來構(gòu)建一個最大堆，在這里為了便于理解趣避，數(shù)組索引為0的節(jié)點不存放數(shù)值庞呕，從第二個節(jié)點開始存放數(shù)據(jù)。
當前節(jié)點的父節(jié)點程帕、左孩子住练、右孩子的索引就會有如下的關(guān)系：
- 父節(jié)點的索引：index/2 (index為當前節(jié)點的索引)
- 左孩子的索引：index*2
- 右孩子的索引：index*2+1
如果從數(shù)組的第一個節(jié)點開始存放數(shù)據(jù)的話，當前節(jié)點的父節(jié)點愁拭、左孩子讲逛、右孩子的索引就會有如下的關(guān)系：
- 父節(jié)點的索引：(index-1)/2 (index為當前節(jié)點的索引)
- 左孩子的索引：index*2+1
- 右孩子的索引：index*2+2
二、優(yōu)先隊列
普通的隊列是一種先進先出的數(shù)據(jù)結(jié)構(gòu)岭埠，元素在隊列尾追加盏混，而從隊列頭刪除。在優(yōu)先隊列中惜论，元素被賦予優(yōu)先級括饶。當訪問元素時，具有最高優(yōu)先級的元素最先刪除。優(yōu)先隊列具有最高級先出 （first in, largest out）的行為特征点弯。通常采用堆數(shù)據(jù)結(jié)構(gòu)來實現(xiàn)僚稿。
三、最大堆的基礎(chǔ)架構(gòu)
3.1 動態(tài)數(shù)組的底層實現(xiàn)
public class Array<E> {
private E[] data;
private int size;
public Array(){
this(10);
}
public Array(int capacity){
this.data = (E[]) new Object[capacity];
this.size = 0;
}
public Array(E[] arr){
this.data = (E[]) new Object[arr.length];
for (int i = 0; i < arr.length; i++) {
data[i] = arr[i];
}
this.size = arr.length;
}
/**
* 獲取數(shù)組中元素個數(shù)
* @return
*/
public int getSize(){
return size;
}
/**
* 獲取數(shù)組容量
* @return
*/
public int getCapacity(){
return data.length;
}
/**
* 返回數(shù)組是否為空
* @return
*/
public boolean isEmpty(){
return size == 0;
}
/**
* 數(shù)組尾部新增元素
* @param e
*/
public void addLast(E e){
add(size, e);
}
/**
* 數(shù)組頭部新增元素
* @param e
*/
public void addFirst(E e){
add(0, e);
}
/**
* 在指定位置插入元素
* @param index
* @param e
*/
public void add(int index, E e){
if(index < 0 || index > size){
throw new IllegalArgumentException("AddLast failed. require index >=0 and index <= size");
}
if(size == data.length){
//擴容
resize(2 * data.length);
}
for(int i = size - 1; i >= index; i --){
data[i + 1] = data[i];
}
data[index] = e;
size ++;
}
/**
* 數(shù)組擴容
* @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;
}
/**
* 獲取指定索引位置的值
* @param index
* @return
*/
public E get(int index){
if(index < 0 || index >= size){
throw new IllegalArgumentException("Get failed. index is illegal.");
}
return data[index];
}
/**
* 替換指定索引位置的值
* @param index
* @param e
*/
public void set(int index, E e){
if(index < 0 || index >= size){
throw new IllegalArgumentException("Set failed. index is illegal.");
}
data[index] = e;
}
/**
* 數(shù)組是否包含元素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;
}
/**
* 查找數(shù)組中元素e所在的索引,不存在元素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;
}
/**
* 刪除數(shù)組中index位置的元素, 并返回刪除的元素
* @param index
* @return
*/
public E remove(int index){
if(index < 0 || index >= size){
throw new IllegalArgumentException("Remove failed. index is illegal.");
}
E ret = data[index];
for (int i = index; i < size - 1; i++) {
data[i] = data[i + 1];
}
size --;
data[size] = null;
if(size == data.length / 4 && data.length / 2 != 0){
//當數(shù)組長度縮小為原數(shù)組的4分之一的時候才進行數(shù)組的縮容技羔，
//縮小為原數(shù)組的2分之一，預(yù)留空間卧抗，防止有數(shù)據(jù)添加導(dǎo)致擴容浪費性能
resize(data.length / 2);
}
return ret;
}
/**
* 刪除數(shù)組中第一個元素
* @return
*/
public E removeFirst(){
return remove(0);
}
/**
* 刪除數(shù)組中最后一個元素
* @return
*/
public E removeLast(){
return remove(size - 1);
}
/**
* 從數(shù)組中刪除元素e
* @param e
*/
public void removeElement(E e){
int index = find(e);
if(index != -1){
remove(index);
}
}
/**
* 數(shù)組索引元素交換
* @param i
* @param j
*/
public void swap(int i, int j){
if(i < 0 || i >= size || j < 0 || j >= size){
throw new IllegalArgumentException("Index is illegal.");
}
E temp = data[i];
data[i] = data[j];
data[j] = temp;
}
@Override
public String toString(){
StringBuilder sb = new StringBuilder();
sb.append(String.format("Array: size = %d, capacity = %d\n",size,data.length));
sb.append("[");
for (int i = 0; i < size; i++) {
sb.append(data[i]);
if(i != size - 1){
sb.append(", ");
}
}
sb.append("]");
return sb.toString();
}
}
3.2 最大堆使用動態(tài)數(shù)組作為底層實現(xiàn)
/**
* @Author: huangyibo
* @Date: 2022/2/17 22:54
* @Description: 最大堆 完全二叉樹藤滥，父親節(jié)點大于等于孩子節(jié)點，采用數(shù)組表示
*/
public class MaxHeap<E extends Comparable<E>> {
//這里使用數(shù)組來實現(xiàn)
private Array<E> data;
public MaxHeap(){
data = new Array<>();
}
public MaxHeap(int capacity){
data = new Array<>(capacity);
}
/**
* 返回堆中的元素個數(shù)
* @return
*/
public int getSize(){
return data.getSize();
}
/**
*堆是否為空
* @return
*/
public boolean isEmpty(){
return data.isEmpty();
}
/**
* 返回完全二叉樹的數(shù)組表示中社裆，一個索引所表示的元素的父親節(jié)點的索引
* @param index
* @return
*/
private int parent(int index){
if(index == 0){
throw new IllegalArgumentException("index-0 doesn't have parent.");
}
return (index - 1) / 2;
}
/**
* 返回完全二叉樹的數(shù)組表示中拙绊，一個索引所表示的元素的左孩子節(jié)點的索引
* @return
*/
private int leftChild(int index){
return index * 2 + 1;
}
/**
* 回完全二叉樹的數(shù)組表示中，一個索引所表示的元素的右孩子節(jié)點的索引
* @param index
* @return
*/
private int rightChild(int index){
return index * 2 + 2;
}
}
3.3 往堆中添加元素
- 在向堆中添加元素時泳秀，除了要維持完全二叉樹的結(jié)構(gòu)标沪，還要注意堆的約束條件：根節(jié)點的值要大于左右子樹的值。
在這里因為我們使用數(shù)組來實現(xiàn)的堆嗜傅，所以添加元素時金句，我們可以先將元素添加到數(shù)組的末尾，然后循環(huán)的與父節(jié)點比較大小吕嘀，比父節(jié)點大就與父節(jié)點交換位置违寞，之后就繼續(xù)與新的父節(jié)點比較大小贞瞒，直到小于等于父節(jié)點。
-
如圖所示趁曼，我們要在這個堆中添加一個元素36军浆。
-
先將元素添加到數(shù)組的末尾。
-
然后通過當前的索引計算出父節(jié)點的索引挡闰，通過索引得到父節(jié)點的值16乒融，通過比較新添加的節(jié)點比其父節(jié)點大，所以將新添加的值與父節(jié)點交換在數(shù)組中的位置尿这。之后再與新的父節(jié)點41比較簇抵，36<41，結(jié)束操作射众。
添加元素的代碼實現(xiàn)
/**
* 向堆中添加元素
* @param e
*/
public void add(E e){
data.addLast(e);
//當前元素在數(shù)組中的索引為 data.getSize() - 1
//比較當前元素和其父親節(jié)點的元素碟摆，大于父親節(jié)點元素則交換位置
siftUp(data.getSize() - 1);
}
/**
* k索引元素比父節(jié)點元素大，則交換位置叨橱，不斷循環(huán)
* @param k
*/
private void siftUp(int k){
//k > 0 并且k索引元素比父節(jié)點元素大典蜕，則交換位置，不斷循環(huán)
while (k > 0 && data.get(parent(k)).compareTo(data.get(k)) < 0){
data.swap(parent(k), k);
k = parent(k);
}
}
3.4 刪除堆頂元素
刪除堆頂元素要注意維持堆的特殊性質(zhì)罗洗。這里舉個例子愉舔。
-
要將這個堆中刪除最大值，也就是堆頂元素62伙菜，先將62取出轩缤。
-
將堆頂元素和堆的最后一個元素互換，也就是數(shù)組的首尾元素互換贩绕。
-
刪除最后一個元素火的，也就是堆中的最大值
-
將當前的堆頂元素16的左右孩子41、30進行比較淑倾，找出最大的一個41馏鹤，再與根節(jié)點16進行比較，左孩子41比根節(jié)點16大娇哆，所以將根節(jié)點與其左孩子互換湃累，如圖所示。
-
重復(fù)上面的操作碍讨，直到當前節(jié)點的值大于其左右子樹治力。過程如下所示。
刪除堆頂元素的代碼實現(xiàn)
/**
* 查看堆中最大元素
* @return
*/
public E findMax(){
if(data.getSize() == 0){
throw new IllegalArgumentException("Can not findMax when heap is empty.");
}
return data.get(0);
}
/**
* 取出堆中最大元素
* @return
*/
public E extractMax(){
//獲取堆中最大元素
E ret = findMax();
//堆中最開始的元素和最后元素交換位置
data.swap(0,data.getSize() - 1);
//刪除堆中最后一個元素
data.removeLast();
//0索引元素比左右孩子節(jié)點元素小垄开，則交換位置琴许，不斷循環(huán)
siftDown(0);
return ret;
}
/**
* k索引元素比左右孩子節(jié)點元素小，則交換位置溉躲，不斷循環(huán)
* @param k
*/
private void siftDown(int k){
while (leftChild(k) < data.getSize()){
//獲取k索引的左孩子的索引
int j = leftChild(k);
//j + 1 < data.getSize()
if(j + 1 < data.getSize() &&
//如果右孩子比左孩子大
data.get(j + 1).compareTo(data.get(j)) > 0){
//最大孩子的索引賦值給j
j = rightChild(k);
}
//此時data[j]是leftChild和rightChild中的最大值
if(data.get(k).compareTo(data.get(j)) >= 0){
//如果父親節(jié)點大于等于左右孩子節(jié)點榜田，跳出循環(huán)
break;
}
//如果父親節(jié)點小于左右孩子節(jié)點(中的最大值)，交換索引的值
data.swap(k, j);
//交換完成之后锻梳，將j賦值給K,重新進入循環(huán)
k = j;
}
}
3.5 Replace操作
Replace是指將堆中的最大元素取出箭券，替換另一個進去。
自然地我們會想到使用之前的extractMax()和add()來實現(xiàn)疑枯，但是這樣的時間復(fù)雜度將會是兩次的O(log n)辩块，因此我們可以直接將堆頂元素替換以后執(zhí)行sift down操作，這樣時間復(fù)雜度就只有O(log n)荆永。
Replace代碼實現(xiàn)
/**
* 取出堆中最大元素废亭，并且替換成元素e
* @param e
* @return
*/
public E replace(E e){
//獲取堆中的最大值
E ret = findMax();
//用新添加的元素替換最大的元素
data.set(0, e);
//0索引元素比左右孩子節(jié)點元素小，則交換位置具钥，不斷循環(huán)
siftDown(0);
return ret;
}
3.6 Heapify操作
Heapify是指將數(shù)組轉(zhuǎn)化為堆豆村。
這里我們先將數(shù)組直接看成是一個完全二叉樹，然后找到這棵二叉樹的最后一個非葉子節(jié)點的節(jié)點骂删，也就是該樹的最后一個節(jié)點的父節(jié)點掌动。然后從這個節(jié)點開始到根節(jié)點結(jié)束，執(zhí)行sift down操作宁玫。這樣的時間復(fù)雜度為O(n)粗恢。
Heapify代碼實現(xiàn)
/**
* 將任意數(shù)組整理成堆的形狀
* @param arr
*/
public MaxHeap(E[] arr){
data = new Array<>(arr);
//從最后一個葉子節(jié)點的父節(jié)點開始進行siftDown操作,不斷循環(huán)
for(int i = parent(arr.length - 1); i >= 0; i --){
siftDown(i);
}
}
至此就完成了整個基于動態(tài)數(shù)組實現(xiàn)的最大堆的全部代碼，完整代碼如下 :
動態(tài)數(shù)組底層實現(xiàn)
/**
* @Author: huangyibo
* @Date: 2021/12/25 17:29
* @Description: 數(shù)組實現(xiàn)
*/
public class Array<E> {
private E[] data;
private int size;
public Array(){
this(10);
}
public Array(int capacity){
this.data = (E[]) new Object[capacity];
this.size = 0;
}
public Array(E[] arr){
this.data = (E[]) new Object[arr.length];
for (int i = 0; i < arr.length; i++) {
data[i] = arr[i];
}
this.size = arr.length;
}
/**
* 獲取數(shù)組中元素個數(shù)
* @return
*/
public int getSize(){
return size;
}
/**
* 獲取數(shù)組容量
* @return
*/
public int getCapacity(){
return data.length;
}
/**
* 返回數(shù)組是否為空
* @return
*/
public boolean isEmpty(){
return size == 0;
}
/**
* 數(shù)組尾部新增元素
* @param e
*/
public void addLast(E e){
add(size, e);
}
/**
* 數(shù)組頭部新增元素
* @param e
*/
public void addFirst(E e){
add(0, e);
}
/**
* 在指定位置插入元素
* @param index
* @param e
*/
public void add(int index, E e){
if(index < 0 || index > size){
throw new IllegalArgumentException("AddLast failed. require index >=0 and index <= size");
}
if(size == data.length){
//擴容
resize(2 * data.length);
}
for(int i = size - 1; i >= index; i --){
data[i + 1] = data[i];
}
data[index] = e;
size ++;
}
/**
* 數(shù)組擴容
* @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;
}
/**
* 獲取指定索引位置的值
* @param index
* @return
*/
public E get(int index){
if(index < 0 || index >= size){
throw new IllegalArgumentException("Get failed. index is illegal.");
}
return data[index];
}
/**
* 替換指定索引位置的值
* @param index
* @param e
*/
public void set(int index, E e){
if(index < 0 || index >= size){
throw new IllegalArgumentException("Set failed. index is illegal.");
}
data[index] = e;
}
/**
* 數(shù)組是否包含元素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;
}
/**
* 查找數(shù)組中元素e所在的索引,不存在元素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;
}
/**
* 刪除數(shù)組中index位置的元素, 并返回刪除的元素
* @param index
* @return
*/
public E remove(int index){
if(index < 0 || index >= size){
throw new IllegalArgumentException("Remove failed. index is illegal.");
}
E ret = data[index];
for (int i = index; i < size - 1; i++) {
data[i] = data[i + 1];
}
size --;
data[size] = null;
if(size == data.length / 4 && data.length / 2 != 0){
//當數(shù)組長度縮小為原數(shù)組的4分之一的時候才進行數(shù)組的縮容欧瘪，
//縮小為原數(shù)組的2分之一眷射，預(yù)留空間，防止有數(shù)據(jù)添加導(dǎo)致擴容浪費性能
resize(data.length / 2);
}
return ret;
}
/**
* 刪除數(shù)組中第一個元素
* @return
*/
public E removeFirst(){
return remove(0);
}
/**
* 刪除數(shù)組中最后一個元素
* @return
*/
public E removeLast(){
return remove(size - 1);
}
/**
* 從數(shù)組中刪除元素e
* @param e
*/
public void removeElement(E e){
int index = find(e);
if(index != -1){
remove(index);
}
}
/**
* 數(shù)組索引元素交換
* @param i
* @param j
*/
public void swap(int i, int j){
if(i < 0 || i >= size || j < 0 || j >= size){
throw new IllegalArgumentException("Index is illegal.");
}
E temp = data[i];
data[i] = data[j];
data[j] = temp;
}
@Override
public String toString(){
StringBuilder sb = new StringBuilder();
sb.append(String.format("Array: size = %d, capacity = %d\n",size,data.length));
sb.append("[");
for (int i = 0; i < size; i++) {
sb.append(data[i]);
if(i != size - 1){
sb.append(", ");
}
}
sb.append("]");
return sb.toString();
}
}
基于動態(tài)數(shù)組底層實現(xiàn)的最大堆實現(xiàn)
/**
* @Author: huangyibo
* @Date: 2022/2/17 22:54
* @Description: 最大堆 完全二叉樹佛掖，父親節(jié)點大于等于孩子節(jié)點妖碉，采用數(shù)組表示
*/
public class MaxHeap<E extends Comparable<E>> {
//這里使用數(shù)組來實現(xiàn)
private Array<E> data;
public MaxHeap(){
data = new Array<>();
}
public MaxHeap(int capacity){
data = new Array<>(capacity);
}
/**
* 將任意數(shù)組整理成堆的形狀
* @param arr
*/
public MaxHeap(E[] arr){
data = new Array<>(arr);
//從最后一個葉子節(jié)點的父節(jié)點開始進行siftDown操作,不斷循環(huán)
for(int i = parent(arr.length - 1); i >= 0; i --){
siftDown(i);
}
}
/**
* 返回堆中的元素個數(shù)
* @return
*/
public int getSize(){
return data.getSize();
}
/**
*堆是否為空
* @return
*/
public boolean isEmpty(){
return data.isEmpty();
}
/**
* 返回完全二叉樹的數(shù)組表示中，一個索引所表示的元素的父親節(jié)點的索引
* @param index
* @return
*/
private int parent(int index){
if(index == 0){
throw new IllegalArgumentException("index-0 doesn't have parent.");
}
return (index - 1) / 2;
}
/**
* 返回完全二叉樹的數(shù)組表示中苦囱，一個索引所表示的元素的左孩子節(jié)點的索引
* @return
*/
private int leftChild(int index){
return index * 2 + 1;
}
/**
* 回完全二叉樹的數(shù)組表示中嗅绸，一個索引所表示的元素的右孩子節(jié)點的索引
* @param index
* @return
*/
private int rightChild(int index){
return index * 2 + 2;
}
/**
* 向堆中添加元素
* @param e
*/
public void add(E e){
data.addLast(e);
//當前元素在數(shù)組中的索引為 data.getSize() - 1
//比較當前元素和其父親節(jié)點的元素，大于父親節(jié)點元素則交換位置
siftUp(data.getSize() - 1);
}
/**
* k索引元素比父節(jié)點元素大撕彤，則交換位置鱼鸠，不斷循環(huán)
* @param k
*/
private void siftUp(int k){
//k > 0 并且k索引元素比父節(jié)點元素大，則交換位置羹铅，不斷循環(huán)
while (k > 0 && data.get(parent(k)).compareTo(data.get(k)) < 0){
data.swap(parent(k), k);
k = parent(k);
}
}
/**
* 查看堆中最大元素
* @return
*/
public E findMax(){
if(data.getSize() == 0){
throw new IllegalArgumentException("Can not findMax when heap is empty.");
}
return data.get(0);
}
/**
* 取出堆中最大元素
* @return
*/
public E extractMax(){
//獲取堆中最大元素
E ret = findMax();
//堆中最開始的元素和最后元素交換位置
data.swap(0,data.getSize() - 1);
//刪除堆中最后一個元素
data.removeLast();
//0索引元素比左右孩子節(jié)點元素小蚀狰，則交換位置，不斷循環(huán)
siftDown(0);
return ret;
}
/**
* k索引元素比左右孩子節(jié)點元素小职员，則交換位置麻蹋，不斷循環(huán)
* @param k
*/
private void siftDown(int k){
while (leftChild(k) < data.getSize()){
//獲取k索引的左孩子的索引
int j = leftChild(k);
//j + 1 < data.getSize()
if(j + 1 < data.getSize() &&
//如果右孩子比左孩子大
data.get(j + 1).compareTo(data.get(j)) > 0){
//最大孩子的索引賦值給j
j = rightChild(k);
}
//此時data[j]是leftChild和rightChild中的最大值
if(data.get(k).compareTo(data.get(j)) >= 0){
//如果父親節(jié)點大于等于左右孩子節(jié)點，跳出循環(huán)
break;
}
//如果父親節(jié)點小于左右孩子節(jié)點(中的最大值)焊切，交換索引的值
data.swap(k, j);
//交換完成之后扮授，將j賦值給K,重新進入循環(huán)
k = j;
}
}
/**
* 取出堆中最大元素芳室，并且替換成元素e
* @param e
* @return
*/
public E replace(E e){
//獲取堆中的最大值
E ret = findMax();
//用新添加的元素替換最大的元素
data.set(0, e);
//0索引元素比左右孩子節(jié)點元素小，則交換位置刹勃，不斷循環(huán)
siftDown(0);
return ret;
}
}
參考：
https://www.cnblogs.com/youch/p/10341675.html
https://blog.csdn.net/love905661433/article/details/82989404
https://blog.csdn.net/weixin_39084521/article/details/90322548
