1、堆及其應用堆的定義(二叉堆)n個關鍵字序列Kl，K2，Kn稱為堆，當且僅當該序列滿足如下性質(簡稱為堆性質)：(1)kiK2i且kiK2i+1或(2)KiK2i且kiK2i+1(1in)。若將此序列所存儲的向量R1.n看做是一棵完全二叉樹的存儲結構，則堆實質上是滿足如下性質的完全二叉樹：樹中任一非葉結點的關鍵字均不大于(或不小于)其左右孩子(若存在)結點的關鍵字堆的定義堆是一棵完全二叉樹，它可分為大根堆和小根堆。根結點(亦稱為堆頂)的關鍵字是堆里所有結點關鍵字中最小者的堆稱為小根堆。根結點(亦稱為堆頂)的關鍵字是堆里所有結點關鍵字中最大者，稱為大根堆。 堆的定義堆的定義： 1.二叉樹的每一個節

2、點存儲一個元素 2.二叉樹的每一個非葉子所存儲元素的優先級高于其兒子存儲的元素的優先級。 堆的樣例105670302515以上就是一個小根堆的樣例堆的樣例703010152556以上就是一個大根堆的樣例堆的定義注意：堆中任一子樹亦是堆。以上討論的堆實際上是二叉堆(BinaryHeap)，類似地可定義k叉堆。 堆的樣例16478953以上就是一個小根堆的樣例堆支持的三種基本操作插入值 Insert 取最小值 Getmin刪除最小值 Deletemin 堆的插入16478953例如：插入一個值為2。插入的過程中始終維護堆性質2堆的插入16478953例如：插入一個值為2。插入的過程中始終維護堆性質

3、2堆的插入16478953例如：插入一個值為2。插入的過程中始終維護堆性質2堆的刪除16478953例如：刪除堆頂元素，并且始終維護堆性質。2堆的刪除6478953例如：刪除堆頂元素，并且始終維護堆性質。2堆的刪除6478953例如：刪除堆頂元素，并且始終維護堆性質。2堆的刪除6478953例如：刪除堆頂元素，并且始終維護堆性質。2堆的刪除6478953例如：刪除堆頂元素，并且始終維護堆性質。2堆的數組實現由于堆有一些特殊的性質，所以我們可以用數組來實現堆。tot保存堆中元素的個數heapi (1=i1時，heapi的父親存放在heapi div 2當中所以任何時刻當堆不為空的時候，堆的最小元

4、素始終存放在heap1的位置。 堆的插入操作代碼實現Procedure Insert(x:longint);var s:integer;begin inc(tot); heaptot:=x; s:=tot; while (s1)and(heapsheaps div 2) do begin swap(heaps,heaps div 2); s:=s div 2; end;End;堆的刪除操作代碼實現Procedure Delete;var s:integer;begin heap1:=heaptot; dec(tot); s:=1; while (s*2=tot) do begin if (s*

5、2=tot) or (heaps*2heapj then begin swap(heaps,heapj); s:=j; end else exit; end;end;堆的各種操作的時間復雜度分析由于用數組實現的堆時刻是一棵近似滿二叉樹，因此插入和刪除的操作時間復雜度僅跟這棵二叉樹的高度有關系。每次操作的復雜度為O(logN)取最小值操作的時間復雜度為O(1).堆堆(heap)堆分為兩種：小根堆和大根堆對于一個線性表s1.n 。小根堆：滿足si=si*2且si=si*2且si=si*2+1堆 性質對于小根堆來說，s1是s1.n中的最小元素。對于大根堆來說，s1是s1.n中的最大元素。 應用范圍查

6、找某個線性表中的最大值和最小值。時間復雜度為O(log2N)。堆堆的維護查找最小(大)值：find := s1插入一個元素key至表s中：totnode:=totnode+1;stotnode:=key;upchange(totnode);堆刪除元素sw：sw:=stotnode;totnode:=totnode-1;downchange(w);兩個操作upchange和downchange堆例題1（堆排序）將n個元素在O(nlogn)的時間復雜度內排序。hash和堆例題（促銷活動） 促銷活動遵守以下規則： 1一個消費者想參加促銷活動的消費者，在賬單下記下他自己所付的費用，他個人的詳細情況，然

7、后將賬單放入一個特殊的投票箱。 2當每天促銷活動結束時，從投票箱中抽出兩張賬單： （1）第一張被抽出的賬單是金額最大的賬單 （2）然后被抽出的是金額最小的賬單，對于付了金額最大賬單的這位消費者，將得到一定數目的獎金，其獎金數等于他賬單上的金額與選出的最小金額的差。 （3）為了避免一個消費者多次獲獎，根據上面所抽出的兩張賬單都不返回到投票箱，但是剩下的賬單還繼續參加促銷活動。hash和堆 超市的售出額是巨大的，這樣可以假定，在每天結束，拿出數額最大賬單和數額最小賬之前，在投票箱內就已經至少存在了2張賬單。 你的任務是去計算每天促銷活動投進投票箱的賬單數額的基本信息。在整個活動中開銷總數。本題中約

8、定：1，整個活動持續了N天(N=5000)。2，第i天放入的帳單有ai張，ai=105。且sigma(a1.an)=106。3，每一天放入的帳單的面值均=106。hash和堆hnoi2005省選第二試最后一題試題分析：hnoi2005第一試最后一題試題分析：5、堆排序堆的定義：n個元素的序列k1,k2,.,kn當且僅當滿足下列條件時，稱之為堆。ki = k2iki = k2i+1或( i = 1, 2, . , n/2 )堆舉例：96,83,27,38,11,09)12,36,24,85,47,30,53,919683381109271236854730245391 堆可以看成是一棵完全二叉樹

9、結點的層次序列,且所有非葉結點的值均不大于(或不小于）左、右孩子結點的值堆排序的基本思想： 對一組待排序的關鍵碼，首先把它們按堆的定義排列成一個序列（稱為建堆），這就找到了最小的關鍵碼，然后將最小的關鍵碼取出，用剩下的關鍵碼再建堆，便得到次最小的關鍵碼，如此反復進行，直到將全部關鍵碼排好序為止。 根結點是堆中的最小元素。 實現堆要解決的問題 1、如何從一個無序序列建成一個堆？ 2、如何在輸出堆頂元素之后，調整剩余元素成為一個新的堆？ 例：圖a是個堆，假設輸出堆頂元素之后，以堆中最后一個元素代之，如圖b。此時根結點的左、右子樹均為堆，則僅需自上至下進行調整即可。1236854730245391(

10、a)9136854730245312(b) 2、如何在輸出堆頂元素之后，調整剩余元素成為一個新的堆？ 首先以堆頂元素和其左、右子樹根結點的值比較之，由于右子樹根結點的值小于左子樹根結點的值且小于根結點的值，則將24和91交換之； 由于91替代了24之后破壞了右子樹的堆，則需要進行和上述相同的調整，直至葉子結點; 重復上述過程，將堆頂元素91和堆中最后一個元素30交換且調整，得到如圖d所示新的堆。 稱這個自堆頂至葉子的調整過程為“篩選”。 91368547302453(c)24368547913053(d)PROC sift（VAR r : listtype; k , m: integer ）;

11、假設r k+1 . . m 中各元素滿足堆的性質，本算法調整r k 使整個序列r k . . m 中各元素滿足堆的性質i : = k ; j : = 2 i ; x : = r k . key ; finished : = fakse ;t : = r k ; 暫存“根”記錄r k WHILE (j=m) AND NOT finished DO IF (j rj+1 . Key) THEN j : = j +1; 若存在右子樹，且右子樹根的關鍵字小，則沿右分支“篩選” IF x 49,則交換之，交換后的序列如圖b所示；49389776132749(a)654938497613652797(b) 同理，在第3個元素65被篩選之后序列的狀態如圖c所示。 由于第2個元素38不大于其左、右子樹根的值，則篩選后的序列不變。 圖e所示為篩選根元素49之后建成的堆。4938497665132797(c)4938497665132797(d)1338497665274997(e)堆排序算法：PROC heapsort（V