堆的性質(zhì)：

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

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

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

   

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

   //size是數(shù)組的大小，index是需要向下調(diào)整的元素的下標(biā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é)點，如果存在的話，只有當(dāng)右節(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)整結(jié)束
        if(array[min] >= array[index]) {
          break;
        }
   
        //交換指定節(jié)點和其子節(jié)點中最小值的節(jié)點
        int tmp = array[index];
        array[index] = array[min];
        array[min] = tmp;
   
        //調(diào)整后下標(biāo)是min的結(jié)點等待繼續(xù)調(diào)整
        index = min;
        left = (index << 1) + 1;
      }
   }

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

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

   3.下述為PriorityQueue在構(gòu)建堆時的源碼：

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

堆最常解決的問題：

• TopK問題
• 排序問題

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

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

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

網(wǎng)站名稱：堆的性質(zhì)是什么？怎么實現(xiàn)堆？-創(chuàng)新互聯(lián)
本文鏈接：http://www.rwnh.cn/article28/ceiecp.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供手機網(wǎng)站建設(shè)、做網(wǎng)站、小程序開發(fā)、網(wǎng)站收錄、電子商務(wù)、外貿(mào)網(wǎng)站建設(shè)

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)