優先隊列(Priority Queue)是一種資料結構，它支援插入(Insert)操作和删除最小值(DeleteMin)或删除最大值(DeleteMax)并傳回删除元素操作。
優先隊列的這些操作等價于隊列的EnQueue和DeQueue操作。
差別在于，對于優先隊列，元素進入隊列的順序可能與其被操作的順序不同。
簡單來說就是優先隊列不一定滿足先入先出的原則，而是根據元素的優先級來進行操作。
如果最小鍵值元素擁有最高的優先級，那麼這種優先隊列叫作升序優先隊列(即總是先删除最小的元素)
如果最大鍵值元素擁有最高的優先級，那麼這種優先隊列叫作降序優先隊列(即總是先删除最大的元素)
- 優先隊列的主要操作
- 優先隊列是元素的容器，每個元素有一個相關的鍵值。
- Insert(key, data)：插入鍵值為key的資料到優先隊列，元素以其key進行排序。
- DeleteMin/DeleteMax：删除并傳回最小/最大鍵值的元素
- GetMin/GetMax：傳回最小/最大鍵值的元素，但不删除該元素
- 第k最小/最大：傳回優先隊列中鍵值為第k個最小/最大的元素
- 大小(Size)：傳回優先隊列中的元素個數
-
堆排序(Heap Sort)：基于鍵值的優先級将優先隊列中的元素進行排序
優先隊列的實作主要讨論二叉堆的實作方式
堆(Heap)是一棵具有特定性質的二叉樹。
堆的基本要求是堆中所有節點的值必須大于等于(或小于等于)其孩子節點的值。
堆還要求當h>0時，所有的葉子節點都處于第h或h-1層(其中h為樹的高度)，也就是說堆是一棵完全二叉樹。
7 1 / \ / \ 3 6 5 2 / \ / / \ / \ 1 2 4 6 1 1 3 該樹是堆，每個節點元素都 這棵樹不是堆，因為5大于其右孩子1 大于其孩子節點的元素
堆的類型：
最小堆：節點值必須小于等于其孩子節點的值
最大堆：節點值必須大于等于其孩子節點的值
1 17
/ \ / \
15 2 13 6
/ \ / \ / \ / \
16 174 3 1 4 2 3
最小堆 最大堆
在二叉堆(Binary Heap)中，每個節點最多有兩個孩子。一般在優先隊列中二叉堆稱作堆(Heap)。
堆的表示：一般使用數組來存儲堆中的元素。例如，最大堆可以表示如下：
data 17 13 6 1 4 2 3
-------------------------
index 0 1 2 3 4 5 6
堆相關的代碼，如下：
/**
* 最大堆
*/
public class Heap {
// 堆元素數組
private int[] array;
// 堆中元素的個數
private int size;
// 堆的大小
private int capacity;
// 堆的類型
private String heap_type;
/**
* 構造方法：根據大小和類型建立堆
*
* @param capacity 堆的大小
* @param heap_type 堆的類型
*/
public Heap(int capacity, String heap_type) {
this.size = ;
this.capacity = capacity;
this.heap_type = heap_type;
this.array = new int[capacity];
}
/**
* 根據節點的位置擷取雙親結點的的位置
*
* 對于第i個位置上的節點，則其雙親節點在(i-1)/2位置上
* @param index 節點的位置
* @return 雙親結點的位置
*/
public int getParentByIndex(int index) {
if ((index < ) || (index >= this.size)) {
return -;
}
return (index - )/;
}
/**
* 根據節點位置擷取左孩子節點的位置
*
* 對于第i個位置上的節點，則其左孩子節點在2*i+1位置上
* @param index 節點位置
* @return 左孩子節點位置
*/
public int leftChild(int index) {
int left = * index + ;
if (left >= this.size) {
return -;
}
return left;
}
/**
* 根據節點位置擷取右孩子節點的位置
*
* 對于第i個位置上的節點，則其右孩子節點在2*i+2位置上
* @param index 節點位置
* @return 右孩子節點位置
*/
public int rightChild(int index) {
int right = * index + ;
if (right >= this.size) {
return -;
}
return right;
}
/**
* 擷取最大元素
*
* 最大堆中的最大元素就是根節點，是以其存儲在數組0号位置
* @return 最大元素
*/
public int getMax() {
if (this.size == ) {
return -;
}
return this.array[];
}
/**
* 堆化目前元素
*
* 當插入或删除一個堆元素時，它可能不滿足堆的性質。
* 在這種情況下就需要調整堆中的元素使之重新變成堆。這一過程叫作堆化(heapifying)
* 在最大堆中，要堆化一個元素，需要找到其孩子節點中的最大值，然後交換元素，重複該過程直到每個節點都滿足堆的性質。
* 這一過程是自頂向下，是以也叫作向下滲透。
* @param index 目前元素的位置
*/
public void percolateDown(int index) {
int max = ;
/* 先擷取目前節點的孩子節點 */
int left = leftChild(index);
int right = rightChild(index);
/* 比較目前節點與其孩子節點的值 */
if ((left != -) && (this.array[left] > this.array[index])) {
max = left;
} else {
max = index;
}
if ((right != -) && (this.array[right] > this.array[max])) {
max = right;
}
/* 如果目前節點不是最大值則交換元素 */
if (max != index) {
int temp = this.array[index];
this.array[index] = this.array[max];
this.array[max] = temp;
/* 遞歸堆化 */
percolateDown(max);
}
}
/**
* 删除堆元素
*
* 删除堆元素，隻需要從根節點删除元素。
* 删除根節點後，将堆的最後一個元素複制到根節點位置，然後删除最後一個元素。
* 當用最後一個元素替換根節點後，可能導緻二叉樹不滿足堆的性質，是以需要堆化根節點元素。
* @return 删除的元素
*/
public int deleteMax() {
/* 先判斷堆是否存在 */
if (this.size == ) {
return -;
}
// 擷取根節點元素
int data = this.array[];
// 将最後一個元素複制到第一個元素位置
this.array[] = this.array[this.size - ];
// 堆的大小減小
this.size--;
/* 堆化根節點元素，即數組第一個位置的元素 */
percolateDown();
// 傳回删除的元素
return data;
}
/**
* 插入元素
*
* 堆的大小增加一
* 将新元素放到堆的尾部
* 從下至上的堆化該元素，也稱作向上滲透
* @param data 插入的新元素
*/
public void insert(int data) {
/* 如果數組容量不夠則擴容 */
if (this.size == this.capacity) {
resizeHeap();
}
// 數組元素個數加一
this.size++;
// 新元素的位置
int index = this.size - ;
/* 堆化元素，向上滲透 */
while ((index >= ) && (data > this.array[(index - ) / ])) {
// 當新元素大于其雙親結點，複制雙親結點到新元素位置
this.array[index] = this.array[(index - ) / ];
// 更新新元素位置
index = (index - ) / ;
}
this.array[index] = data;
}
/**
* 清空堆
*/
public void destroyHeap() {
this.size = ;
this.array = null;
}
/**
* 數組建堆
*
* 先将數組元素插入空堆中，不考慮堆的性質。
* 因為葉子節點總是滿足堆的性質，無需關注它們。
* 葉子節點元素總是在最後面，是以要對給定的數組建堆，隻需要堆化葉子節點即可。
*
* 堆的最後一個元素所處的位置為size-1,通過最後一個元素的雙親節點就能找到第一個非葉子節點((size-1)-1)/2。
* @param heap 堆
* @param array 數組
*/
public void buildHeap(Heap heap, int[] array) {
// 擷取數組的大小
int n = array.length;
/* 如果堆不存在則傳回 */
if (heap == null) {
return;
}
/* 如果堆的容量不夠則擴容 */
while (n > this.capacity) {
heap.resizeHeap();
}
/* 先将數組元素存入堆中 */
for (int i = ; i < n; i++) {
this.array[i] = array[i];
}
// 設定堆的大小
this.size = n;
// 堆化非葉子節點元素
for (int i = (n-)/; i >= ; i--) {
heap.percolateDown(i);
}
}
/**
* 堆排序
*
* 堆排序算法首先将所有元素插入堆中，然後從堆中依次删除根節點元素，直到堆為空
* @param array 無序數組
* @return 排序後的數組
*/
public int[] heapSort(int[] array) {
// 擷取數組大小
int n = array.length;
// 建立堆
Heap heap = new Heap(n, "big");
// 數組建堆
heap.buildHeap(heap, array);
int temp = ;
for (int i = ; i < n; i++) {
// 擷取根節點元素
temp = heap.array[];
// 将最後一個元素複制到第一個元素位置
heap.array[] = heap.array[heap.size - ];
// 堆的大小減小
heap.size--;
/* 堆化根節點元素，即數組第一個位置的元素 */
heap.percolateDown();
// 存儲删除的元素
array[i] = temp;
}
return array;
}
/**
* 内部方法：堆擴容
*/
private void resizeHeap() {
// 建立新的數組，大小為原來數組的兩倍
int[] newArray = new int[ * capacity];
// 複制原數組到新數組
System.arraycopy(this.array, , newArray, , this.size);
// 重置數組容量
capacity = capacity * ;
// 複制給原數組，也就是使array指向新生成記憶體
array = newArray;
}
getter/setter......
}
![【資料結構】 醫院選址[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)