Java實現的二叉堆以及堆排序詳解
一、前言
二叉堆是一個特殊的堆，其本質是一棵完全二叉樹，可用數組來存儲數據，如果根節點在數組的下標位置為1，那麼當前節點n的左子節點為2n，有子節點在數組中的下標位置為2n+1。二叉堆類型分為最大堆（大頂堆）和最小堆（小頂堆），其分類是根據父節點和子節點的大小來決定的，在二叉堆中父節點總是大於或等於子節點，該二叉堆成為最大堆，相反地稱之為最小堆。因此，最大堆父節點鍵值大於或等於子節點，最小堆父節點鍵值小於或等於子節點。根據二叉堆的特點，二叉堆可以用來實現排序、有限隊列等。堆排序就是利用二叉堆的特性來實現的。二叉堆數據結構如下：
二、相關概念
（一）、樹
樹是一種重要的非線性數據結構，直觀地看，它是數據元素（在樹中稱為結點）按分支關係組織起來的結構，很象自然界中的樹那樣。一棵樹（tree）是由n（n>0）個元素組成的有限集合，其中：
（二）、二叉樹
1、完全二叉樹
非完全二叉樹
三、二叉堆插入節點和刪除節點
（一）、插入節點
思路：因為二叉堆是用數組來存儲數據的，所以每次插入節點時，實際是往數組數據尾部增加數據。但是，如果直接往尾部放數據，有可能破壞【父節點鍵值大於或等於子節點】的特性，因此，每次插入數據時都需要將二叉堆從新堆化的操作。堆化過程就是插入節點和父節的鍵值進行比較，如果父節點鍵值小於插入節點，則需要將兩個節點進行交換，然後繼續向上比較，直至父節點不小於插入節點或到達根節點。流程圖如下：
程式碼實現如下：
/**
* 插入節點
* @param value 鍵值
* @return 成功或失敗
*/
public boolean put(int value) {
/**
* 數組已滿
*/
if (size > capacity) {
return false;
}
//直接將新節點插入到數據尾部
data[size] = value;
//插入節點後不滿足二叉堆特性，需要重新堆化
maxHeapify(size++);
return true;
}
/**
* 大頂堆堆化
* @param pos 堆化的位置
*/
private void maxHeapify(int pos) {
/**
* parent 堆化位置的父節點；計算公式：父節點=子節點*2
* 向上堆化過程
*/
for (int parent = pos >> 1;parent > 0 && data[parent] < data[pos];pos = parent,parent = parent >> 1) {
swap(parent,pos);
}
}
/**
* 數組數據交換
* @param i 下標
* @param j 下標
*/
private void swap(int i,int j) {
int tmp = data[i];
data[i] = data[j];
data[j] = tmp;
}
測試結果如下：
(二）、刪除節點
刪除節點主要用於堆排序的功能，因為每次刪除節點時都是刪除堆頂節點（即最大值或最小值），當整個二叉堆刪除完成就可以得到一個有序的數組或列表。堆刪除節點一般都是刪除根節點，根節點被刪除後該樹就不滿足二叉堆的特性，所以需要重新調整堆，使之成為一個真正的二叉堆。調整堆結構有多種方式，我這裡說的是一種比較簡便，高效的方式。大致的思路：將堆頂節點和最後一個節點交換，然後刪除最後一個節點。交換節點鍵值後就不滿足二叉堆的特性了，所以需要重新調整。根節點為父節點，與兩個子節點鍵值進行比較，找到鍵值最大的節點後交換父節點和該節點的位置。位置交換後以最大值所在節點看作父節點，繼續與子節點比較。當父節點均大於子節點或到達葉子節點時，即完成堆化過程。流程圖如下：
通過上面的4個步驟後就可以將堆頂元刪除掉。具體程式碼實現如下：
/**
* 刪除元素
* @return
*/
public int remove() {
int max = data[1];
if (size < 1) {
return -1;
}
swap(1,size);
size--;
shiftDown(1);
return max;
}
/**
* 自上而下重新調整二叉堆
* @param pos 開始調整位置
*/
private void shiftDown(int pos) {
int left = pos << 1;
int right = left + 1;
int maxPos = pos;
if (left <= size && data[left] > data[maxPos]) {
maxPos = left;
}
if (right <= size && data[right] > data[maxPos]) {
maxPos = right;
}
if (pos == maxPos) {
return;
}
swap(pos,maxPos);
shiftDown(maxPos);
}
測試結果：
public static void main(String[] args) {
Heap heap = new Heap(5);
Scanner scanner = new Scanner(System.in);
while (scanner.hasNext()) {
String next = scanner.next();
if (next.equalsIgnoreCase("r")) {
heap.remove();
}else {
heap.put(Integer.parseInt(next));
}
System.out.println(heap.toString());
}
}
//列印結果
1
[1]
2
[2,1]
3
[3,1,2]
4
[4,3,2,1]
5
[5,4,2,1,3]
r
[4,3,2,1]
r
[3,1,2]
r
[2,1]
r
[1]
r
[]
完成程式碼：
/**
* @className: Heap
* @description: 堆
* @author: rainple
* @create: 2020-09-01 15:39
**/
public class Heap {
/**
* 數組容量
*/
private int capacity;
/**
* 數據大小
*/
private int size;
/**
* 數據
*/
private int[] data;
public Heap(int capacity) {
if (capacity <= 0) {
throw new IllegalArgumentException("參數非法");
}
this.capacity = capacity;
data = new int[capacity + 1];
}
/**
* 插入節點
* @param value 鍵值
* @return 成功或失敗
*/
public boolean put(int value) {
/**
* 數組已滿
*/
if (size + 1 > capacity) {
return false;
}
//直接將新節點插入到數據尾部
data[++size] = value;
//插入節點後不滿足二叉堆特性，需要重新堆化
maxHeapify(size);
return true;
}
/**
* 大頂堆堆化
* @param pos 堆化的位置
*/
private void maxHeapify(int pos) {
/**
* parent 堆化位置的父節點；計算公式：父節點=子節點*2
* 向上堆化過程
*/
for (int parent = pos >> 1;parent > 0 && data[parent] < data[pos];pos = parent,parent = parent >> 1) {
swap(parent,pos);
}
}
/**
* 刪除元素
* @return
*/
public int remove() {
int max = data[1];
if (size < 1) {
return -1;
}
swap(1,size);
size--;
shiftDown(1);
return max;
}
/**
* 自上而下重新調整二叉堆
* @param pos 開始調整位置
*/
private void shiftDown(int pos) {
int left = pos << 1;
int right = left + 1;
int maxPos = pos;
if (left <= size && data[left] > data[maxPos]) {
maxPos = left;
}
if (right <= size && data[right] > data[maxPos]) {
maxPos = right;
}
if (pos == maxPos) {
return;
}
swap(pos,maxPos);
shiftDown(maxPos);
}
/**
* 數組數據交換
* @param i 下標
* @param j 下標
*/
private void swap(int i,int j) {
int tmp = data[i];
data[i] = data[j];
data[j] = tmp;
}
@Override
public String toString() {
if (size == 0) {
return "[]";
}
StringBuilder builder = new StringBuilder("[");
for (int i = 1; i < size + 1; i++) {
builder.append(data[i]).append(",");
}
return builder.deleteCharAt(builder.length() - 1).append("]").toString();
}
}
四、堆排序
（一）、演算法實現
堆排序是利用了堆這種數據結構的特性而設計出來的高效的排序演算法。演算法實現也並不是很難，排序的過程就是將堆頂元素與最後一個元素交換的過程，每次交換後都需要進行一次堆結構使之成為一顆新的二叉堆。其實，排序的過程類似與我們上面講到的刪除節點的過程，每進行一次刪除操作，都會將根節點（最大值或最小值）放在當前堆對應的數組的最後一個位置，當所有節點都進行一次刪除後即可得到一個有序的數組，如果大頂堆最後數組的正序排序，小頂堆則是倒敘排序。下面我使用圖例來演示排序的過程，因為過程中涉及到堆化過程而且上面也演示過了，所以下面只演示初始和結束兩個狀態：
程式碼實現如下：
public static void sort(int[] data) {
int len = data.length - 1;
//將數組構建成一顆二叉堆
build(data,len);
while (len > 0) {
//數組第一個元素和二叉堆中最後一個元素交換位置
swap(data,0,len);
//堆化
heapify(data,0,--len);
}
}
/**
* 建堆
* @param data 數據
* @param len 長度
*/
private static void build(int[] data,int len){
for (int i = len >> 1;i >= 0;i--) {
heapify(data,i,len);
}
}
/**
* 堆化
* @param data 數據
* @param start 開始位置
* @param end 結束位置
*/
private static void heapify(int[] data,int start,int end){
while (true){
int max = start;
int left = max << 1;
int right = left + 1;
if (left <= end && data[max] < data[left]) {
max = left;
}
if (right <= end && data[max] < data[right]){
max = right;
}
if (max == start) {
break;
}
swap(data,start,max);
start = max;
}
}
/**
* 將data數組中i和j的數據互換
* @param data 數據
* @param i 下標
* @param j 下標
*/
private static void swap(int[] data,int i,int j){
int tmp = data[i];
data[i] = data[j];
data[j] = tmp;
}
（二）、堆排序時間複雜度
堆排序時間複雜度需要計算初始化堆和重建堆的時間複雜度。
初始化堆的複雜度：假如有N個節點，那麼高度為H=logN，最後一層每個父節點最多只需要下調1次，倒數第二層最多只需要下調2次，頂點最多需要下調H次，而最後一層父節點共有2^(H-1)個,倒數第二層公有2^(H-2),頂點只有1(2^0)個，所以總共的時間複雜度為s = 1 * 2^(H-1) + 2 * 2^(H-2) + … + (H-1) * 2^1 + H * 2^0；將H代入後s= 2N – 2 – log2(N)，近似的時間複雜度就是O(N)。
重建堆時間複雜度：循環 n -1 次，每次都是從根節點往下循環查找，所以每一次時間是 logn，總時間：logn(n-1) = nlogn – logn
綜上所述，堆排序的時間複雜度為 O（nlogn）
(三）、堆排序時間測試
生成100萬個隨機數進行排序，排序總花費時間為：280毫秒
1000萬隨機數排序平均花費時間大概是3s多。
