算法學習之路|資料結構--堆

堆（英語：heap)是計算機科學中一類特殊的資料結構的統稱。堆通常是一個可以被看做一棵樹的數組對象。堆總是滿足下列性質：

堆中某個節點的值總是不大于或不小于其父節點的值；

堆總是一棵完全二叉樹。

将根節點最大的堆叫做最大堆或大根堆，根節點最小的堆叫做最小堆或小根堆。常見的堆有二叉堆、斐波那契堆等。

堆的定義如下：n個元素的序列{k1,k2,ki,…,kn}當且僅當滿足下關系時，稱之為堆。

(ki <= k2i,ki = k2i,ki >= k2i+1), (i = 1,2,3,4...n/2)

若将和此次序列對應的一維數組（即以一維數組作此序列的存儲結構）看成是一個完全二叉樹，則堆的含義表明，完全二叉樹中所有非終端結點的值均不大于（或不小于）其左、右孩子結點的值。由此，若序列{k1,k2,…,kn}是堆，則堆頂元素（或完全二叉樹的根）必為序列中n個元素的最小值（或最大值）。

ps：以上定義來自百度百科

1.保持堆的性質

該操作主要用于維持堆的基本性質。假定以節點t的左孩子節點和節點t的右孩子節點為根的子樹都已經是堆，然後調整以t為根的子樹，使之成為堆。

2.建堆

操作主要是将數組A轉化成一個大頂堆。思想是，先找到堆的最後一個非葉子節點（即為第n/2個節點），然後從該節點開始，從後往前逐個調整每個子樹，使之稱為堆，最終整個數組便是一個堆。

3.堆排序

先用BuildHeapo将數組A[1..n]構造成一個最大堆。再将最大的元素A[1]和A[n]交換，再數組A[1..n-1]構造成一個最大堆，直到排序完成

4.優先隊列

優先隊列是一種用來維護由一組元素構成的集合S的資料機構。相信大家對它都有所了解。雖然說c++裡面有了priority_queue,但我們還是要了解它的一些基本構成及實作的代碼。

GETMAX:

該操作主要是擷取堆中最大的元素，同時保持堆的基本性質。堆的最大元素即為第一個元素，将其儲存下來，同時将最後一個元素放到A[1]位置，之後從上往下調整A，使之成為一個堆

INSERT:

向堆中添加一個元素t，同時保持堆的性質。算法思想是，将t放到A的最後，然後從該元素開始，自下向上調整，直至A成為一個大頂堆。