堆的性質(zhì)：

• 堆在邏輯上是一棵完全二叉樹
• 堆是基于數(shù)組實現(xiàn)的，堆的所有元素都存儲在數(shù)組中
• 滿足任意結點的值都大于其子樹中結點的值的堆，稱為大堆
• 滿足任意結點的值都小于其子樹中結點的值的堆，稱為小堆
• 堆的基本作用是快速的在集合中找到最值

堆的實現(xiàn)（小堆為例）：

1. 堆的向下調(diào)整(siftDown)：為了滿足小堆的性質(zhì)，即任意結點的值都小于其子樹中結點的值，因此需要對指定結點進行向下調(diào)整，代碼如下：

   

   創(chuàng)新互聯(lián)建站服務項目包括翼城網(wǎng)站建設、翼城網(wǎng)站制作、翼城網(wǎng)頁制作以及翼城網(wǎng)絡營銷策劃等。多年來，我們專注于互聯(lián)網(wǎng)行業(yè)，利用自身積累的技術優(yōu)勢、行業(yè)經(jīng)驗、深度合作伙伴關系等，向廣大中小型企業(yè)、政府機構等提供互聯(lián)網(wǎng)行業(yè)的解決方案，翼城網(wǎng)站推廣取得了明顯的社會效益與經(jīng)濟效益。目前，我們服務的客戶以成都為中心已經(jīng)輻射到翼城省份的部分城市，未來相信會繼續(xù)擴大服務區(qū)域并繼續(xù)獲得客戶的支持與信任！

   //size是數(shù)組的大小，index是需要向下調(diào)整的元素的下標
   public void siftDown(int[] array, int size, int index) {
      int left = (index << 1) + 1;
      //堆是完全的二叉樹，如果沒有左節(jié)點，那么必定沒有右節(jié)點，因此以左節(jié)點作為先決條件
      while(left < size) {
        //先假定最小的值時左節(jié)點的值
        //原因:進入循環(huán)左節(jié)點必定存在，然后再判斷右節(jié)點是否存在，
        //不存在的話最小值肯定是左節(jié)點，如果存在的話，只有當右節(jié)點的值小于左節(jié)點時才會讓最小值時右節(jié)點的值
        int min = left;
        int right = (index << 1) + 2;
   
        //只有右節(jié)點存在且小于左節(jié)點的值時才進入循環(huán)
        if(right < size && array[right] < array[left]) {
            min = right;
        }
   
        //如果兩子節(jié)點中的最小值都大于他本身的值時，調(diào)整結束
        if(array[min] >= array[index]) {
          break;
        }
   
        //交換指定節(jié)點和其子節(jié)點中最小值的節(jié)點
        int tmp = array[index];
        array[index] = array[min];
        array[min] = tmp;
   
        //調(diào)整后下標是min的結點等待繼續(xù)調(diào)整
        index = min;
        left = (index << 1) + 1;
      }
   }

2. 構建堆(heapify)：從最后一個非葉子結點開始向下調(diào)整直到根節(jié)點(下標為0的元素)后，表示任意結點都滿足了小堆的性質(zhì)，實現(xiàn)方式如下：

   //此處size是數(shù)組最后一個元素的下標
   public void heapify(int[] array, int size) {
      for (int i = (size - 1) >> 1; i >= 0; i--) {
        new SiftDown().siftDown(array, size, i);
      }
   }

   3.下述為PriorityQueue在構建堆時的源碼：

   //其中size表示的是數(shù)組中元素的個數(shù)，因此和上面構建代碼中的循環(huán)條件有所差別，但是本質(zhì)表達的是一個意思
   private void heapify() {
      for (int i = (size >>> 1) - 1; i >= 0; i--)
        siftDown(i, (E) queue[i]);
   }

堆最常解決的問題：

• TopK問題
• 排序問題

堆的應用—優(yōu)先級隊列：

• 提供兩個最基本的操作，一個是返回最高優(yōu)先級對象，一個是添加新的對象。這種數(shù)據(jù)結構就是優(yōu)先級隊列(Priority Queue)
• 優(yōu)先級隊列的實現(xiàn)方式有很多，但是最常見的是使用堆來構建
• Java中的優(yōu)先級隊列就是通過構建堆來實現(xiàn)的

另外有需要云服務器可以了解下創(chuàng)新互聯(lián)scvps.cn，海內(nèi)外云服務器15元起步，三天無理由+7*72小時售后在線，公司持有idc許可證，提供“云服務器、裸金屬服務器、高防服務器、香港服務器、美國服務器、虛擬主機、免備案服務器”等云主機租用服務以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡單易用、服務可用性高、性價比高”等特點與優(yōu)勢，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應用場景需求。