先提個問題，完全二叉樹/滿二叉樹，區別？前者是指每一層都是緊湊靠左排列，最後一層可能未排滿，後者是一種特殊的完全二叉樹，
每層都是滿的，即節點總數和深度滿足N=(2^n) -1。堆Heap，一堆蘋果，為了賣相好，越好看的越往上放，就是大頂堆；為了蘋果堆
的穩定，質量越小越往上放，就是小頂堆；堆首先是完全二叉樹，但只確保父節點和子節點大小邏輯，不關心左右子節點的大小關係，
通常是一個可以被看做一棵樹的數組對象，是個很常見的結構，比如BST對象，都與堆有關係，今天就說下這個重要的數據結構和應用。
作者原創文章，謝絕一切轉載，違者必究！
本文只發表在”公眾號”和”博客園”，其他均屬複製粘貼！如果覺得排版不清晰，請查看公眾號文章。
準備：
Idea2019.03/Gradle6.0.1/Maven3.6.3/JDK11.0.4
難度： 新手–戰士–老兵–大師
目標：
1.堆的構建和調整算法
1 優先級隊列
為理解堆的原理，先看優先級隊列，它是一種數據結構，插入或者刪除元素的時候，元素會自動排序，(優先級不是狹義的數值大小，
但為了通俗理解，這裏以字母序為例)，通常使用數組存儲，我們可以按照下圖進行轉換，序號 0 不用：
優先級隊列的實現(Java版)：
public class PriorityQueue<Key extends Character> {
/** 存儲元素的數組 */
private Key[] keys;
private int N = 0;
public PriorityQueue(int capacity){
// 下標0不用，多分配一個單位
keys = (Key[]) new Character[capacity + 1];
}
public Key max(){
return keys[1];
}
public void insert(Key e){
N ++;
keys[N] = e;
swim(N);
}
public Key delMax(){
Key max = keys[1];
swap(1,N);
keys[N] = null;
N --;
// 讓第一個元素下沉到合適的位置
sink(1);
return max;
}
/** 上浮第k個元素*/
private void swim(int k){
// 比父節點小，即進行交換，直到根
while (k > 1 && less(parent(k),k)){
swap(k,parent(k));
k = parent(k);
}
}
/** 下沉第 k 個元素*/
private void sink(int k){
while(k < N){
int small = left(k);
if (right(k) < N && less(right(k),left(k))){
small = right(k);
}
if (less(k,small)){
swap(k,small);
k = small;
}
}
}
private void swap(int i,int j){
Key temp = keys[i];
keys[i] = keys[j];
keys[j] = temp;
}
/** 元素i和j大小比較*/
private boolean less(int i,int j){
// 'a' - 'b' = -1 ;
return keys[i].compareTo(keys[j]) > 0;
}
/** 元素i的父節點*/
private int parent(int i){
return i/2;
}
/** 元素i的左子節點*/
private int left(int i){
return i * 2;
}
/** 元素i的右子節點*/
private int right(int i){
return i * 2 + 1;
}
}
以上代碼解析：
1 swim 上浮，對於元素k，是否需要上浮，僅需與其父節點比較，大於父節點則交換，迭代直到根節點；
2 sink 下沉，對於元素k，是否需要下沉，需先比較其左右子節點，找出左右子節點中較小者，較小者若比父節點大，則交換，迭代直到末尾元素；
3 insert 插入，先將元素放到數組末尾位置，再對其進行上浮操作，直到合適位置；
4 delMax 刪除最大值，大根堆，故第一個元素最大，先將首末元素交換，再刪除末尾元素，再對首元素下沉操作，直到合適位置；
總結：以上只是Java簡化版，java.util.PriorityQueue 是JDK原版，客官可自行研究。但設計還是非常有技巧的，值得思考一番，假設 insert 插入
到首位，會導致數組大量元素移動。delMax 若直接刪除首位最大值，則需要進一步判斷左右子節點大小，並進行先子節點上浮再首元素下沉操作。
有了這個堆結構，就可以進行堆排序了，將待排數全部加入此堆結構，然後依次取出，即成有序序列了！
2 堆排序
如要求不使用上述堆數據結構。思路(升序為例)：將數組構建為一個大頂堆，首元素即為數組最大值，首尾元素交換；排除末尾元素后調整大頂堆，
則新的首元素即為次最大值，交換首尾並再排除末尾元素；如此循環，最後的數組即為升序排列。
public class HeapSort02 {
public static void main(String []args){
int []arr = {2,1,8,6,4,7,3,0,9,5};
sort(arr);
System.out.println(Arrays.toString(arr));
}
public static void sort(int []arr){
int len = arr.length;
// 創建一個大頂堆
for(int i = (int) Math.ceil(len/2 - 1); i >= 0; i--){
//從第一個非恭弘=叶 恭弘子結點從下至上，從右至左調整結構
adjustHeap(arr,i,len);
}
// 交換首尾元素，並重新調整大頂堆
for(int j = len-1;j > 0;j--){
swap(arr,0,j);
adjustHeap(arr,0,j);
}
}
/** 迭代寫法*/
public static void adjustHeap(int []arr,int i,int length){
int temp = arr[i];
for (int k = 2*i + 1; k < length; k=k*2 + 1) {
// 注意這裏的k + 1 < length
// 如果右子節點大於左子節點，則比較對象為右子節點
if (k + 1 < length && arr[k] < arr[k+1]){
k++;
}
if (arr[k] > temp){
// 不進行值交換
arr[i] = arr[k];
i = k;
}
else{
break;
}
}
arr[i] = temp;
}
/** 遞歸寫法*/
private static void adjustHeap2(int[] arr, int i, int len){
int left = 2 * i + 1;
int right = 2 * i + 2;
int maxIndex = i;
// 注意這裏的 left < len
if (left < len && arr[left] > arr[maxIndex]){
maxIndex = left;
}
if (right < len && arr[right] > arr[maxIndex]){
maxIndex = right;
}
if (maxIndex != i){
swap(arr,i,maxIndex);
adjustHeap2(arr,maxIndex,len);
}
}
/** 交換元素 */
public static void swap(int []arr,int a ,int b){
int temp=arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
}
以上代碼解析：
1完全二叉樹結構中，如果根節點順序號為 0，總節點數為 N，則最末節點的父節點即為最後一個非恭弘=叶 恭弘子節點，順序號為 ceil(N/2 -1)，
2 adjustHeap2 為啥使用三個參數，不用中間的參數可以？使用三個參數，是為了進行遞歸調用，因為遞歸肯定是縮小計算規模，而這裏的形參arr和len是固定不變的；
3 adjustHeap是非遞歸寫法，不用中間的參數可以？調用一在“構建大頂堆”處，可寫為函數體內初始化 i，並形成雙重 for 循環；調用二在“重新調整大頂堆”處，
可見中間參數為 0，可直接去掉。故回答是可以！但需要調整寫法，且影響該方法復用，這裏直接寫為三個形參的函數更為優雅而已。
4非遞歸寫法理解：類似插入排序思想(依次移動並找到合適的位置再插入)，先將 arr[i] 取出，然後此節點和左右子樹進行比較，如子樹更大則子節點上升一層，使
用for循環迭代到最終位置，並進行賦值；
以 i=0 為例：
5遞歸方式理解：定位目標元素的左右子樹，若子樹值更大，則進行值交換，且因為子樹發生了變化，故需要對子樹進行遞歸處理；
3 前K個最大的數
在N個數中找出前K個最大的數： 思路：從N個數中取出前K個數，形成一個數組[K]，將該數組調整為一個小頂堆，則可知堆頂為K個數中最小值，
然後依次將剩餘 N-K 個數與堆頂比較，若大於，則替換掉並調整堆，直到所有元素加入完畢，堆中元素即為目標集合。
public class HeapSort {
public static void main(String[] args) {
int[] arr = new int[100];
for (int i = 0; i < 100; i++) {
arr[i] = i + 1;
}
// 前10個最大的數
int k = 10;
// 構造小頂堆
for (int i = (int) Math.ceil(k/2 - 1); i >= 0; i--) {
adjustHeap(arr,i,k);
}
// 依次比較剩餘元素
for (int i = 10; i < arr.length; i++) {
if (arr[i] > arr[0]){
swap(arr,0,i);
adjustHeap(arr,0,k);
}
}
// 輸出結果
for (int i = 0; i < 10; i++) {
System.out.print(arr[i]+"-");
}
}
/** 非迭代寫法 ,對arr[i]進行調整 */
private static void adjustHeap(int[] arr,int i,int length){
int temp = arr[i];
for (int k = i * 2 + 1; k < length; k = k * 2 + 1) {
// 因第一次循環中可能越界，故需要 k+1 < length
if (k + 1 < length && arr[k] > arr[k + 1]){
k++;
}
if (arr[k] < temp){
arr[i] = arr[k];
i = k;
}
else {
break;
}
}
arr[i] = temp;
}
/** 遞歸寫法 */
private static void adjustHeap2(int[] arr,int i,int length){
int left = i * 2 + 1;
int right = i * 2 + 2;
int samller = i;
if (left < length && arr[left] > arr[samller]){
samller = right;
}
if (right < length && arr[right] > arr[samller]){
samller = right;
}
if (samller != i){
swap(arr,i,samller);
adjustHeap2(arr,samller,length);
}
}
/** 交換元素 */
public static void swap(int []arr,int a ,int b){
int temp=arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
}
以上代碼解析：按照”初始化—構建小頂堆—比較調整—輸出結果”執行。注意for循環中，因第一次循環中未使用for語句條件判斷，可能越界，故需要 k+1 < length。
輸出結果如下：
請看官思考，如果需求變為找出N個數中找出前K個最小的數,該如何實現? 建議動腦且動手的寫一遍！因為魔鬼在細節！
全文完！
我近期其他文章：
- 1 Dubbo學習系列之十九（Apollo配置中心）
- 2 聊聊算法——二分查找算法深度分析
- 3 DevOps系列——Jenkins/Gitlab自動打包部署
- 4 DevOps系列——Jenkins私服
- 5 DevOps系列——Gitlab私服
只寫原創，敬請關注
本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理
【其他文章推薦】
※網頁設計一頭霧水該從何著手呢? 台北網頁設計公司幫您輕鬆架站!
※網頁設計公司推薦不同的風格，搶佔消費者視覺第一線
※Google地圖已可更新顯示潭子電動車充電站設置地點!!
※廣告預算用在刀口上，台北網頁設計公司幫您達到更多曝光效益
※別再煩惱如何寫文案,掌握八大原則!
電動車電池的成本下降速度超乎預期，甚至低於國際能源署（IEA）原本預估的 2020 年成本數值，且不少研究也指出，太陽能在 2020 年代將某些地區成為最便宜的能源選項，彭博新聞認為，便宜的電池與太陽能發電兩者相輔相成的結果，將加速再生能源主宰能源市場的趨勢。 國際能源署在 2013 年時，原本預估 2020 年電動車電池價格將會下降至每度電 300 美元，不過，由斯德哥爾摩環境機構最近登上《自然氣候變化（Nature Climate Change）》期刊的研究中指出，全球電動車電池價格已從 2007 年的每千瓦小時 1,000 美元，下降至 2014 年的每千瓦小時 410 美元，平均每年成本下滑 14%，且特斯拉（Tesla）及 Nissan 等電動車製造商領頭羊的價格也年減約 8%，來到 2014 年的每千瓦小時 300美元，提早 6 年達到國際能源署預定目標。 但這所謂的每千瓦小時 300 美元，除了顯示電動車電池成本下降速度超乎預期外，是否還意味著電動車躍起的時代即將來臨呢？全球顧問公司麥肯錫（Mckinsey & Company）在 2011 年曾做了一張圖表，顯示不同的油價與電池價格情況下，純電動車、插電式混合電動車、油電混合車及一般汽車何者較具競爭力，灰色區塊的部分則是 2011 年的價格區間。從下圖圖表中可以看出，當電動車電池價格位於每千瓦小時約 300 美元左右時，就是電動車競爭力逐漸起飛的時刻。 
