APP
完整代碼參見github
堆的概念
定義
堆就是一棵二叉樹，每個節(jié)點包含一個鍵，不過還需要滿足以下兩個條件：
（1）必須是完全二叉樹，也就是說，樹的每一層都必須是滿的，除了最后一層最右邊的元素可能有所缺失
（2）堆特性（又稱為父母優(yōu)勢，這里我們以最大堆為例），每一個節(jié)點都要大于或等于它的子節(jié)點（對于葉子節(jié)點我們認(rèn)為是滿足這個條件的）
舉例說明，上圖中只有第一棵樹是堆，第二棵樹違背了完全二叉樹條件，第三棵樹也不是堆，因為節(jié)點5小于它的子節(jié)點6，堆特性條件不滿足。
需要注意的是，從根到某葉子節(jié)點的路徑上，鍵值的序列是遞減的（非遞增）的，但是同一層的節(jié)點之間或者不同層之間無父子（或祖先后代）關(guān)系的節(jié)點之間美哦與任何順序聯(lián)系！
堆的特征
堆的構(gòu)造
經(jīng)典的堆構(gòu)造往往采用數(shù)組的實現(xiàn)方式，并且下標(biāo)從1開始（數(shù)組第一個元素閑置）
堆的構(gòu)造方法通常有兩種，一種是元素逐個進行插入，另一個是用heapify對整個數(shù)組進行初始化。
1 插入構(gòu)造法
代碼如下：
#include <iostream>
#include <algorithm>
#include <cassert>
template <typename Item>
class MaxHeap {
private:
Item* data;
//堆的實際容量（不包括data[0]）
int capacity;
//堆目前的元素數(shù)量
int count;
void shiftUp(int index) {
while (index > 1) {
if (data[index] > data[index / 2])
std::swap(data[index],data[index / 2]);
index /= 2;
}
}
void shiftDown(int index) {
while (index * 2 <= count) {
int j =2 * index;
if (j + 1 <= count && data[j] < data[j + 1]) {
j++;
}
if (data[j] <= data[index]) {
break;
}
std::swap(data[j],data[index]);
index = j;
}
}
public:
MaxHeap(int capacity) {
this -> capacity = capacity;
data = new Item[capacity + 1];
count = 0;
}
~MaxHeap() {
delete [] data;
}
//插入元素
void insert(Item item) {
assert(count < capacity);
data[++count] = item;
//將item浮動到合適的位置
shiftUp(count);
}
//彈出根元素
Item pop() {
assert(count > 0);
Item root = data[1];
data[1] = data[count];
count--;
shiftDown(1);
return root;
}
void print() {
for (int i = 1; i <= count; i++) {
std::cout << data[i] << " ";
}
}
//獲取堆的當(dāng)前大小
int size() {
return count;
}
//判斷堆是否為空
bool isEmpty() {
return count == 0;
}
};
將nnn個元素逐個插入到堆中，時間復(fù)雜度為O(nlogn)O(nlogn)O(nlogn)
接下來我們就可以直接利用最大堆的根節(jié)點最大的特點編寫堆排序
堆排序-版本一
template <typename T>
template heapSort1(T arr[],int n){
MaxHeap<T> maxHeap = MaxHeap<T>(n);
for (int i = 0;i < n;i++){
maxHeap.insert(arr[i]);
}
for (int i = n - 1;i >= 0;i--){
arr[i] = maxHeap.pop();
}
}
Heapify將數(shù)組轉(zhuǎn)換為堆結(jié)構(gòu)
之前我們都是將元素逐個加入到數(shù)組中，然后利用shiftUp進行堆結(jié)構(gòu)的整理，但更好的做法是直接在原數(shù)組中將數(shù)組整理為堆結(jié)構(gòu)，這個過程叫做Heapify
我們將原來不滿足堆結(jié)構(gòu)的數(shù)組以完全二叉樹的結(jié)構(gòu)進行表示，如下圖所示：
通過觀察，可以發(fā)現(xiàn)，所有的葉子節(jié)點都滿足堆結(jié)構(gòu)，從第一個不是葉子節(jié)點的節(jié)點（索引為5的節(jié)點22）開始不滿足堆結(jié)構(gòu)，因此，從該節(jié)點開始我們不斷進行shiftDown操作，直到根節(jié)點，這樣我們就完成了對數(shù)組進行堆結(jié)構(gòu)整理的操作。
我們將該過程整理成MaxHeap類的另一個構(gòu)造方法，代碼如下：
//利用數(shù)組進行堆的初始化
MaxHeap(Item arr[],int n) {
data = new Item[n + 1];
this -> capacity = n;
this -> count = n;
for (int i = 0; i < n; i ++) {
data[i + 1] = arr[i];
}
//從第一個不是葉子節(jié)點的節(jié)點開始向上，逐次使用shiftDown方法
for (int i = count / 2; i > 0 ; i --) {
shiftDown(i);
}
}
用heapipy方法，時間復(fù)雜度為O(n)O(n)O(n)
堆排序-版本二
template <typename T>
template heapSort2(T arr[],int n){
MaxHeap<T> maxHeap = MaxHeap<T>(arr,n);
for (int i = n - 1;i >= 0;i--){
arr[i] = maxHeap.pop();
}
}
堆排序-最終版
//堆排序算法--最終版
//在原數(shù)組中進行堆排序，不占用額外空間
//首先對原數(shù)組進行heapify
//然后將arr[0]和最后一個元素進行交換，重新對第一個元素進行heapify，以此類推
//注意：索引從0開始
//左子樹：2 * i + 1
//右子樹：2 * i + 2
//父節(jié)點：(i - 1) / 2
#include <iostream>
#include <cassert>
template <typename T>
void __shiftDown(T arr[],int n,int index) {
while (2 * index + 1 < n) {
int j = 2 * index + 1;
if (j + 1 < n && arr[j] < arr[j + 1])
j++;
if (arr[index] > arr[j]) {
break;
}
std::swap(arr[index],arr[j]);
index = j;
}
}
template <typename T>
void heapSort(T arr[] ,int n) {
//從第一個不是葉子節(jié)點的元素開始向上，對每個節(jié)點進行shiftDown
for (int i = (n - 1) / 2; i >= 0; i--) {
__shiftDown(arr, n, i);
}
for (int i = n - 1; i > 0 ; i --) {
std::swap(arr[i], arr[0]);
__shiftDown(arr, i, 0);
}
}
索引堆
什么是索引堆？
與普通堆只存儲元素不同，索引堆是將元素和其索引同時存儲的數(shù)據(jù)結(jié)構(gòu)（多用一個數(shù)組來保存元素的索引）。
為什么需要索引堆？
我們以普通堆為例進行說明，普通堆構(gòu)造之前的數(shù)據(jù)存儲如下圖所示
我們用數(shù)組存儲堆的元素，隨后我們將數(shù)組進行堆構(gòu)造
我們看到，數(shù)組以堆的形式進行了重構(gòu)，但這在某些特殊情形下可能會帶來一些麻煩。
比如，我們存儲的元素是一篇上萬字的文章，那么對文章進行交換位置的開銷是相當(dāng)大的；再比如，原始數(shù)組的元素表示的是計算機的進程，其數(shù)組索引表示的該進程的id號，當(dāng)我們按照堆對其進行重構(gòu)之后，我們無法確定排列之后的元素（進程）的id號是多少，因此諸如改變某個id為3的進程的優(yōu)先級的這種操作便不太靈活（除非我們對存儲的元素進行數(shù)據(jù)結(jié)構(gòu)封裝，使其同時存儲id號，但同樣還是帶來了元素交換的效率問題），這時候我們的索引堆就派上了用場。
索引堆的構(gòu)造
這里我們?nèi)匀灰宰畲蠖褳槔?/p>
索引堆底層用兩個數(shù)組進行表示，一個用來存儲元素的索引（數(shù)組從索引1開始存儲），另一個（數(shù)組從索引1開始存儲）用來存儲元素，我們對存儲索引的數(shù)組進行堆的構(gòu)造(對int類型的數(shù)據(jù)進行交換是很高效的)，存儲元素的數(shù)組我們不改變其存儲的順序，圖示如下：
我們用heapify對索引數(shù)組進行堆構(gòu)造，完成之后的圖示如下：
代碼如下：
#include <iostream>
#include <algorithm>
#include <cassert>
template <typename Item>
class IndexMaxHeap{
private:
//存儲元素的數(shù)組
Item* data;
//存儲元素索引的數(shù)組
int* indexes;
//當(dāng)前堆中元素個數(shù)
int count;
//堆容量
int capacity;
void shiftUp(int i){
while(i > 1){
if (data[indexes[i]] > data[indexes[i / 2]]){
std::swap(indexes[i],indexes[i / 2]);
}
i /= 2;
}
}
void shiftDown(int i){
int j = 0;
while (2 * i <= count){
j = 2 * i;
if (j + 1 <= count && data[indexes[j]] < data[indexes[j + 1]])
j += 1;
if (data[indexes[i]] >= data[indexes[j]])
break;
std::swap(indexes[i],indexes[j]);
i = j;
}
}
public:
IndexMaxHeap(int capacity){
data = new Item[capacity + 1];
indexes = new int[capacity + 1];
this -> capacity = capacity;
this -> count = 0;
}
~IndexMaxHeap(){
delete [] data;
delete [] indexes;
}
int size(){
return count;
}
//注意，對用戶而言，i是從0開始的，但我們存儲是從1開始，編程實需要注意
void insert(int i,Item item){
assert(count < capcacity);
assert(i > 0 && i + 1 < capcacity);
data[++i] = item;
indexes[++count] = i;
shiftUp(count);
}
Item pop(){
assert(count > 0);
Item root = data[indexes[1]];
indexes[1]=indexes[count];
count--;
shiftDown(1);
return root;
}
//返回最大元素的索引
int popMaxIndex(){
assert(count > 0);
//注意，對用戶來說從0開始
int root = indexes[1] - 1;
indexes[1] = indexes[count];
std::swap(indexes[1],indexes[count]);
count--;
shiftDown(1);
return root;
}
Item getItem(int i){
return data[i + 1];
}
//修改索引為i的item
//O(n)
void change(int i,Item newItem){
data[++i] = newItem;
//接下來我們需要找到newItem(即data[i]在indexes中的位置)
//indexes[j] = i,j表示的就是data[i]在堆中的位置
//將i嘗試shiftUp操作或者shiftDown
for (int j = 1;j < count; j++){
if (indexes[j] == i ){
shiftUp(j);
shiftDown(j);
}
}
}
}
這里我們在class中加入了一個比較常用的操作change，將data中索引為i的元素改為newItem，我們采用遍歷indexes的做法來找到indexes的下標(biāo)j，這個j表示的是我們更改的newItem的索引在indexes中的存儲位置，即
??data[index[j]] = newIndex??
這樣一來change操作的時間復(fù)雜度就是O(n)O(n)O(n)
能不能有更快的操作方法呢？
reverse表
如上圖，rev數(shù)組就是index（就是indexes）數(shù)組的一個reverse表（當(dāng)然反過來說也是正確的），其實就是索引和元素值的調(diào)換而已，
index[i] = j;
reverse[j] = i;
但經(jīng)過這樣存儲，我們可以通過O(1)O(1)O(1)的時間復(fù)雜度找到index中的索引。
舉個例子：
假如我更改了data數(shù)組中下標(biāo)為4的元素13的值為100，那么為了維持堆的性質(zhì)，data數(shù)組可以不變，我們必須對index數(shù)組進行重構(gòu)，那我們就需要知道100的下標(biāo)（4）在index中的存儲位置j，然后對j進行??shiftUp???或??shiftDown??試探（總有一個會有效）。
如果我們不用reverse表的方法，我們需要從頭遍歷index數(shù)組，直到我們遇到??index[j] == 4???,此時我們得到 ??j=9??。
如果我們采用reverse表的方式，我們要找4在index中的存儲位置，直接利用??reverse[4]??就可以得到，時間復(fù)雜度為O(1)O(1)O(1)
詳細(xì)代碼見ReverseIndexMaxHeap.h
###最后一點優(yōu)化 我們上面寫的代碼中，getItem(int i)?和change(int i,Item newItem)?函數(shù)其實有一點小瑕疵，如果我們輸入的參數(shù)i并沒有存儲在indexes數(shù)組中，那么我們的程序就會出錯
因此我們需要編寫一個函數(shù)來檢驗i?是否在堆（indexes）中，這里我們用到了reverse數(shù)組 詳細(xì)代碼見?ReverseIndexMaxHeap.h
bool isContains(int i){
assert(i + 1 >=1 && i + 1 <=capacity);
return reverse[i + 1] != 0;
}本文摘自 ：https://blog.51cto.com/u
