資訊專欄INFORMATION COLUMN
摘要：堆排序的時間復雜度非常的穩定，是，并且是原地排序算法，具體是怎么實現的呢我們一般把堆排序分為兩個步驟建堆和排序。
1. 什么是堆
堆（Heap），其實是一種特殊的二叉樹，主要滿足了二叉樹的兩個條件：
堆是一種完全二叉樹，還記得完全二叉樹的定義嗎？葉節點都在最底下兩層，最后一層的節點都靠左排列，并且除了最后一層，其他層的節點個數都要達到最大，這種樹叫做完全二叉樹。
堆中的每個節點的值都必須大于等于（或者小于等于）其左右子節點的值。
對于堆中的每個節點都大于等于其左右子節點的值，叫做大頂堆，反之，則叫做小頂堆?？纯聪旅娴膱D就能懂了。
其中，1 是大頂堆，2 是小頂堆，3 不是堆。
2. 堆是如何存儲的？
其實，堆可以按照完全二叉樹的存儲方式來儲存，因為完全二叉樹是比較省空間的，所以我們可以直接用數組來存儲，然后按照數組下標來取出堆中數據。參照下圖，來看看堆的存儲：
其中，對于任意位置上的節點 i ，其左子節點是 2 * i + 1，右子節點是 2 * i + 2，父節點是 (i - 1) / 2。
3. 堆的幾種操作
明白了堆是怎樣儲存的，我們在來看看堆最常見的兩個操作：往堆中插入元素和刪除堆頂元素。
首先，如果要往堆中插入一個元素，我們先將其插入到數組中最后一個位置，然后與其父節點的值進行比較，如果大于父節點，則交換位置，繼續比較?？纯聪旅娴膱D你就明白了：
交換操作的代碼，我也放到這里：
public class Heap {
private int[] data;//存儲堆數據的數組
private int n;//堆中可存儲的元素容量
private int size;//堆中存儲的元素個數
public Heap(int capacity) {
this.data = new int[capacity];
this.n = capacity;
this.size = 0;
}
//往堆中插入數據
public void insert(int value){
if (size >= n) return;//堆滿了
data[size] = value;
int i = size;
while ((i - 1) / 2 >= 0 && data[i] > data[(i - 1) / 2]){
//交換data[i] 極其父節點 data[(i - 1) / 2] 的值
swap(data, i, (i - 1) / 2);
i = (i - 1) / 2;
}
size ++;
}
//交換數組兩個位置的元素
private void swap(int[] data, int i, int j){
int temp = data[i];
data[i] = data[j];
data[j] = temp;
}
}
接下來看看第二種操作：刪除堆頂元素。
根據堆的定義，堆頂元素其實就是堆的最大或最小元素。所以刪除堆頂元素，我們只需要移除數組中的第 0 個元素，然后再進行堆化，讓堆繼續保持順序。那該怎么進行堆化呢？
首先我們直接將堆中的最后一個元素移到堆頂，然后與其左右子節點的值進行比較，找到較大的那么子節點，交換位置，然后繼續比較，你可以結合代碼來理解一下：
//刪除數據，如果是大頂堆，則刪除的是堆中的最大元素
//如果是小頂堆，則刪除的堆中的最小元素
public int removeMax(){
if (size == 0) return -1;//堆為空
//將數組中的最后一個元素，放到第一個位置
int result = data[0];
data[0] = data[size - 1];
data[-- this.size] = 0;
//進行堆化
heapify(data, size, 0);
return result;
}
//堆化函數
private void heapify(int[] data, int size, int i){
while (true){
int max = i;
if ((2 * i + 1) < size && data[i] < data[2 * i + 1]) max = 2 * i + 1;
if ((2 * i + 2) < size && data[max] < data[2 * i + 2]) max = 2 * i + 2;
if (max == i) break;
swap(data, i, max);
i = max;
}
}
4. 堆排序
現在來看看里用堆這種數據結構是怎么實現排序功能的。堆排序的時間復雜度非常的穩定，是O(nlogn)，并且是原地排序算法，具體是怎么實現的呢？我們一般把堆排序分為兩個步驟：建堆和排序。
建堆
對于一個未排序的數組，例如 data[3,5,8,2,1,4,6]，其原始的結構是這樣的：
可以看到第一個非葉子節點是 8，所以我們從 8 開始從上往下堆化，然后依次是 5 - 3，堆化后的效果就是這樣的：
這樣，我們就將一個無序的數組堆化成了具有堆的性質的數據，還需要說明以下，如果確定一個堆的第一個非葉子節點是多少呢？實際上，對于長度為 length 的數組，(length - 2) / 2下標對應的數據，就是堆中的第一個非葉子節點。接下來的操作就是排序了。
排序
排序的過程類似于上面說到的刪除堆頂元素，因為堆頂元素是堆的最大或最小元素，以大頂堆為例，我們只需要將堆頂元素和數組中最后一個元素交換位置，然后重新構造堆，繼續交換堆頂元素和數組中最后一個未排序數據，知道堆中元素剩下最后一個。
示意圖如下：
整個建堆和排序的實現的代碼也貼在這里：
//堆排序
public void heapSort(int[] data){
int length = data.length;
if (length <= 1) return;
//建堆
buildHeap(data);
while (length > 0){
swap(data, 0, --length);
heapify(data, length, 0);
}
}
//建堆
//從非葉子節點依次堆化
private void buildHeap(int[] data){
int length = data.length;
for (int i = (length - 2) / 2; i >= 0; -- i) {
heapify(data, length, i);
}
}
文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。
轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/74035.html
摘要：之所以把歸并排序快速排序希爾排序堆排序放在一起比較，是因為它們的平均時間復雜度都為。歸并排序是一種穩定的排序方法。因此，快速排序并不穩定。希爾排序思想先將整個待排序的記錄序列分割成為若干子序列。 showImg(https://segmentfault.com/img/bVbvpYZ?w=900&h=250); 1. 前言 算法為王。 想學好前端，先練好內功，只有內功深厚者，前端之路才...
摘要：二叉堆數據結構是一種特殊的二叉樹，他能高效快速的找出最大值和最小值，常應用于優先隊列和著名的堆排序算法中。 二叉堆數據結構是一種特殊的二叉樹，他能高效、快速的找出最大值和最小值，常應用于優先隊列和著名的堆排序算法中。 二叉堆 二叉堆有以下兩個特性： 是一顆完全二叉樹，表示數的每一層都有左側和右側子節點（除最后一層的葉節點），并且最后一層的葉節點盡可能是左側子節點 二叉堆不是最小堆就是...
摘要：前面介紹了七大算法的思想與實現步驟，下面來做一個歸總。直到無序區中的數為零，結束排序。步驟以從小到大為例，排序數組大小為。比較完以后則排序結束。堆排序思想堆排序是采用樹的形式的數據結構來進行排序的，其中每一個堆都是完全二叉樹。 前面介紹了七大算法的思想與實現步驟，下面來做一個歸總。 排序方法 平均復雜度 最壞復雜度 最好復雜度 輔助空間 穩定性 直接選擇排序 O(n^2...
摘要：一虛擬機內存圖解程序運行與虛擬機之上，運行時需要內存空間。是一種數據結構，是虛擬機中的局部變量表，對應物理層之上的程序數據模型。 一：虛擬機內存圖解 JAVA 程序運行與虛擬機之上，運行時需要內存空間。虛擬機執行 JAVA 程序的過程中會把它管理的內存劃分為不同的數據區域方便管理。 虛擬機管理內存數據區域劃分如下圖： showImg(https://segmentfault.com/i...
摘要：筆者寫的數據結構與算法之美系列用的語言是，旨在入門數據結構與算法和方便以后復習。這應該是目前較為簡單的十大經典排序算法的文章講解了吧。比如原本在的前面，而，排序之后，在的后面十大經典排序算法冒泡排序思想冒泡排序只會操作相鄰的兩個數據。 showImg(https://segmentfault.com/img/bVbvHet); 1. 前言 算法為王。想學好前端，先練好內功，內功不行，就...
閱讀 3209·2021-11-12 10:36
閱讀 1258·2019-08-30 15:56
閱讀 2444·2019-08-30 11:26
閱讀 551·2019-08-29 13:00
閱讀 3609·2019-08-28 18:08
閱讀 2749·2019-08-26 17:18
閱讀 1893·2019-08-26 13:26
閱讀 2432·2019-08-26 11:39
