點擊上方 "程序員小樂"關注, 星標或置頂一起成長
每天凌晨00點00分, 第一時間與你相約
每日英文
Sometimes,God does not give you what you want,it is not because you do not deserve it but for the better.
有時候，上天沒有給你想要的，不是因為你不配，而是你值得更好的。
每日掏心話
有人說人生無奈，但人定勝天，我們可以改變。的確，也許唯有充實人生，才能彌補一些遺憾不足，讓自己快樂多一點煩惱少一點。
來自：CoderJed | 責編：樂樂
鏈接：jianshu.com/p/3e1d4ed98565
程序員小樂(ID:study_tech)第 739 次推文 圖片來自 Pexels
往日回顧：Java泛型背後是什麼？
正文
1. 圖示過程
大根堆的性質：
堆頂的數一定是所有元素的最大值
任何一顆子樹的根元素一定是該子樹的最大元素
某節點的左右葉子節點是無序的
大根堆與數組的關係：計算機中是沒有堆或者樹這種概念的，堆或者樹需要使用基本的數據結構來實現，用數組表示一個大根堆的規律如下：
數組索引為 0 的位置存放堆頂的元素
數組索引為 i 的元素的左右葉子節點的索引是 2 * i + 1 和 2 * i + 2
數組索引為 i 的元素的父節點的下標索引為 (i - 1) / 2
(1) 堆排序整體流程
首先把數組中的 N 個數建成一個大小為 N 的大根堆
然後把堆頂的數和堆的最後一個數交換：
此時數組的最後一個值就是最大值
然後把推中的最後一個元素剔除，把剩餘的元素再次調整為一個大根堆
然後把堆頂元素與最後一個元素交換位置
此時數組的倒數第二個元素就是數組中第二大的元素。
重複以上過程，當堆的大小為 1 的時候，數組就有序了。
(2) 堆化過程
將一個數組轉化為一個大根堆的過程稱為堆化，堆化的過程如下：
原數組對應的數結構為：
從第一個元素開始遍歷，只要它的值比父節點大，就把它和父節點相互交換。
2. 展示
3. Java代碼實現
public static void heapSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
for (int i = 0; i < arr.length; i++) {
heapInsert(arr, i);
}
int size = arr.length;
swap(arr, 0, --size);
while (size > 0) {
heapify(arr, 0, size);
swap(arr, 0, --size);
}
}
public static void heapInsert(int[] arr, int index) {
while (arr[index] > arr[(index - 1) / 2]) {
swap(arr, index, (index - 1) / 2);
index = (index - 1) / 2;
}
}
/**
* 堆化
*/
public static void heapify(int[] arr, int index, int size) {
int left = index * 2 + 1;
while (left < size) {
int largest = left + 1 < size && arr[left + 1] > arr[left] ? left + 1 : left;
largest = arr[largest] > arr[index] ? largest : index;
if (largest == index) {
break;
}
swap(arr, largest, index);
index = largest;
left = index * 2 + 1;
}
}
public static void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
4. 複雜度
時間複雜度：O(nlogn)
空間複雜度：O(1), 只需要一個額外的空間用於交換元素
穩定性：堆排序無法保證相等的元素的相對位置不變，因此它是不穩定的排序算法
歡迎在留言區留下你的觀點，一起討論提高。如果今天的文章讓你有新的啟發，學習能力的提升上有新的認識，歡迎轉發分享給更多人。
猜你還想看
阿里、騰訊、百度、華為、京東最新面試題彙集
Redis Sentinel 架構原理詳解
Java 會走向晦暗嗎？Kotlin 會取而代之嗎
一次SQL優化的體驗
關注「程序員小樂」，收看更多精彩內容
嘿，你在看嗎？
閱讀更多 程序員小樂 的文章
