前言

• heap這種數據結構，允許用戶以任何次序將任何數據放入該結構中，但是最后取出數據的時候一定是權值最高（或者最低）的元素。主要和實現有關，根據比較方法的不同，實現大根堆/小根堆的算法……

  下面小編主要是實現大根堆的算法。

• 并且如果一個類型需要進行使用堆來進行存儲，那么這個類型一定是支持比較方法的。

本文章就和大家來探討堆的算法。例如：

1. push_heap
2. pop_heap
3. sort_heap
4. make_heap

1. heap結構概述

• heap的底層就是使用的一個完全二叉樹（邏輯上）。我們使用vector/array容器來作為heap的底層結構，再以順序結構構建這顆完全二叉樹（物理存儲上）。

• 大根堆：任意一個父節點的權值都大于等于孩子節點的權值。

• 小根堆：任意一個父節點的權值都小于等于孩子節點的權值。

• 構建的方式：

  1. 我們將這顆二叉樹的根設置為數組的0下標。（還有其它設置方法）

  2. 根節點找孩子節點：

     當前節點的下標為i，左孩子的下標為2 * i + 1；右孩子的下標為：2 * i + 2。合理地找到一個根節點左右孩子節點。

  3. 孩子節點找根節點：

  當前節點的下標為i，父親節點的下標為(i - 1)/2。

• 現有如圖的大根堆結構：

  

2. push_heap

push_heap操作是在原有的堆基礎之上，再在這個完全二叉樹的結構中添加的新的元素，一般而言會有如下的幾個步驟：

1. 將新數據新增到物理結構的最后下標位置，但是邏輯結構上仍然是一個完全二叉樹。此時，已經破壞了大根堆/小根堆的性質。

2. 需要對當前節點的數據進行調整，使得整個完全二叉樹滿足大根堆/小跟堆的性質。

   此時我們用到的調整算法：Percolate Up（上溯）。向上調整。

如下圖：

• 調整的結束：當前節點權值小于等于父節點權值或者已經更新到根節點。

	void push_heap(int val){_heap.push_back(val); //添加新元素AdjustUp(_heap.size() - 1);}void AdjustUp(size_t child){int index = (int)child; //拿到最后一個位置的下標while (index > 0) //當前調整的節點位置大于0，就繼續調整{int parent = (index - 1) / 2; //找到父節點位置if (_heap[parent] < _heap[index]) //父親節點的key < 當前節點位置的key{//交換兩者的權值std::swap(_heap[parent], _heap[index]);}else // >={break;}//調整當前位置的下標index = parent;}}

3. pop_heap

一般來說，pop的操作是取走整個heap的權值最大/最小的節點。根據前面的經驗，那么就是需要將根節點的數據取走。根節點在vector中的下標為0。我們該如何取取走該根節點呢？

• 為了滿足堆的完全二叉樹的性質，所以pop節點一定是最后一個位置的。那么我們能想到的方案就是：

  1. 交換根節點權值和最后一個節點的權值，執行pop_back。此時整個heap結構仍然保持完全二叉樹結構。但是不滿足大根堆/小根堆性質。

  2. 我們需要對根節點開始調整，使其滿足堆的性質。

     從根節點開始，執行 Percolate Down(下溯)。向下調整。

如下圖：

• 調整的結束：當前節點權值小于左右孩子最大節點值或者沒有左右孩子。

void pop_heap()
{size_t index = _heap.size() - 1;std::swap(_heap[0], _heap[index]); //交換權值_heap.pop_back(); //刪除最后一個元素AdjustDown(0, _heap.size() - 1); //傳入根節點的下標和當前heap的有效長度
}void AdjustDown(int index, int size)
{//在完全二叉樹中，左孩子存在，但是右孩子不一定存在int child = index * 2 + 1; //假設左孩子大while (child < size) //選取的孩子不能越界；越界了說明孩子不存在{if (child + 1 < size && _heap[child] < _heap[child + 1]){child = child + 1; //更新左右孩子中值較大的}if (_heap[index] < _heap[child]) //父親比孩子小{std::swap(_heap[index], _heap[child]); //交換權值//繼續向下調整}else // >={break;}//更新index和childindex = child;child = 2 * index + 1;}
}

后面的sort_heap會解釋，為什么向下調整還需要一個size的參數

4. sort_heap

• 堆排序的思想：

  利用堆的性質：每次都能獲得當前heap中鍵值最大的元素。結合pop_heap算法我們可以可以持續對堆中的元素做pop_heap操作。（注意：這里的pop_heap不會將原有的數據刪除，而是有效數據的位置減少，在pop_heap中的size參數，就是體現有效數據的地方）這樣我們每次都能將鍵值最大/最小的元素安置在容器的末尾，從而完成升序或者降序……

  注意：使用完堆排序之后，這個heap就不再是一個heap了

void sort_heap()
{int size = (int)_heap.size(); //得到當前大小while (size > 1) //剩余元素超過兩個{// 模擬pop_backint index = size - 1;std::swap(_heap[0], _heap[index]);--size; //有效長度-1//向下調整AdjustDown(0, size); //向下調整有效長度}
}

5. make_heap

• 建堆一般是根據一個已有的容器/迭代器中的數據，將這些數據構建出一個大根堆/小根堆的算法。很容易我們可以想到一種方法：

  方案一：依次將迭代器區間中的元素push_heap到一個新的堆中。

但是這樣的建堆方式是利用了向上調整的算法。這個算法要求，除了最后一個位置之外的所有位置，都滿足堆結構。后面會進行時間復雜度的分析。

• 如果你比較敏銳，你會發現我們向下調整的算法，要求：當前節點的左右子樹必須滿足堆結構。

  方案二：我們可以局部看待任何一個二叉樹，分為左子樹 根 右子樹。為了實現向下調整的算法。我們似乎的處理方式是：先將左右子樹建堆，最后根向下調整。以任何一個。這樣的建堆方式如下圖：

我們采用迭代的方式進行建堆，即：找到沒有成堆的最小樹開始向下調整。

void make_heap()
{int index = (int)_heap.size() - 1, size = (int)_heap.size(); //堆數據的大小int parent = (index - 1) / 2; //找到父親節點while (parent >= 0) //實際上調整的節點是父親節點{AdjustDown(parent, size);--parent; //遍歷下一個父親節點}
}

• 時間復雜度分析：
  

完。