Heap

Heap(堆積)是一個陣列，可以把它看作類似完全二元樹(也就是按照順序排放的樹)。
p.s : 樹是一種資料結構，大部分的操作時間複雜度平均為樹將在後面介紹~~

樹上每一個節點，對應到陣列中的一個元素。除了樹的最底層以外，該樹是完全填滿的，填充的規則為由左向右進行填充。

表示Heap的陣列通常會具有兩個屬性，表示陣列中元素的個數，表示Heap中元素的個數。

樹的根結點為，給定陣列的index i進行走訪，可以根據index來得到樹的父節點，左子節點和右子節點

PARENT(i)
    return i/2
LEFT_CHILD(i)
    return 2i
RIGHT_CHILD(i)
    return 2i + 1

假設i = 2，則LEFT_CHILD = 4，元素為8，RIGHT_CHILD = 5，元素為7，PARENT = 2，元素為14。

二元堆積(Binary heap)可以分成兩種，最大堆積(max heap)和最小堆積(min heap)，在這兩種heap中，都需要滿足heap的性質。

• 最大堆積(max heap) : 父節點的值>=子節點的值,
• 最小堆積(min heap) : 父節點的值<=子節點的值,

以上面這個例子，即為max heap。但是有可能有一個heap不屬於上面這兩種，假設陣列沒有先經過排序，只會產生出heap，他不屬於max heap，也不屬於min heap。

在heap sort中，通常會使用max heap。min heap通常用來實作priority heap。在特定的應用中，才會明確的說使用的是min heap還是max heap，當兩者皆可時，通常直接以heap來描述。

如果直接把heap當作一棵樹，定義一個heap中的節點高度為某一個節點由上往下找到達葉節點所經過的最大邊數，如2號節點其高度為2。而拓展這個定義，可以得到整個heap的高度為樹根到業節點所經過的最大邊數，因此這個heap的高度為3。

一個包含n個元素的陣列可以看做一個完全二元樹，那麼該heap的高度為。對於heap的操作基本上和樹的高度成正比，也就是時間複雜度為，以下為一些針對heap的操作

• MAX-HEAPIFY : 用於維持max heap的性質，時間複雜度為
• BUILD-MAX-HEAP : 將無序的陣列轉變成一個max heap。
• HEAPSORT : 對一個陣列進行原地(in place)排序，

以下操作是針對priority heap

• MAX-HEAP-INSERT : 插入一個元素到heap
• HEAP-EXTRACT-MAX : 回傳最大值，並將該最大值從heap中移除
• HEAP-INCREASE-KEY : 把x對應到的權重(鍵值)增加到k上面
• HEAP-MAXUNIUM : 回傳最大值

MAX-HEAPIFY

MAX-HEAPIFY是用來維持max heap。他的參數為陣列A和一個下標i。

呼叫MAX-HEAPIFY時，會假定根節點的兩棵子樹結點LEFT(i)和RIGHT(i)都符合max heap，如果不符合，便將的值在max heap中一階一階的下降，直到A[i]的兩棵子樹LEFT(i)和RIGHT(i)都符合max heap。

如果我們呼叫MAX-HEAPIFY(Array, 2)，會發現他的值並不大於LEFT(i)，這並不符合max heap的規則，因此，交換和的值，讓第2號節點符合max heap的性質。

在上一步的操作雖然讓第2號節點符合max heap的規則，但是它使第4號節點違反max heap的規則，因此，遞迴呼叫MAX-HEAPIFY(A, 4)，發現比RIGHT(i)還要小，因此交換和。

交換之後，遞迴呼叫MAX-HEAPIFY(A, 9)，發現條件皆不成立，因此甚麼都不做。

虛擬碼如下

MAX-HEAPIFY(A, i)
    l = LEFT(i)
    r = RIGHT(i)
    if l <= A.heap-size and A[l] > A[i]
        largest = l
    else largest = i
    if r <= A.heap-size and A[r] > A[largest]
        largest = r
    if largest != i
        exchange A[i] with A[largest]
        MAX-HEAPIFY(A, largest)

MAX-HEAPIFY效率

對於一棵以i為根節點，大小為n的子樹，MAX-HEAPIFY所需要的時間代價為，調整,和之間的關係時間複雜度為，加上在一棵以i的一個子節點產生出的子樹呼叫MAX-HEAPIFY的時間，每個子節點所產生的子樹大小最大為(會發生在樹的底層恰好為半滿的時候)，可以用下面的遞迴關係式表示MAX-HEAPIFY的執行時間:

，使用主定理得到，含有個元素的heap高度為，也就是說，對於高度為的heap來說，MAX-HEAPIFY的效率為。

BUILD-MAX-HEAP

由下而上透過呼叫MAX-HEAPIFY將一個大小為的陣列轉變成max heap。子陣列中的元素皆為樹的葉節點。每一個葉節點可以當作是只有一個元素heap。透過由下而上不斷呼叫MAX-HEAPIFY完成BUILD-MAX-HEAP。

BUILD-MAX-HEAP(A)
A.heap-size = A.length
for i = A.length/2 downto 1
    MAX-HEAPIFY(A, i)

1. 呼叫MAX-HEAPIFY(A, 5)
   
2. 呼叫MAX-HEAPIFY(A, 4)
   
3. 呼叫MAX-HEAPIFY(A, 3)
   
4. 呼叫MAX-HEAPIFY(A, 2)
   
5. 呼叫MAX-HEAPIFY(A, 1)
   
   完成
   

BUILD-MAX-HEAP效率

每一次呼叫MAX-HEAPIFY根據上面的推導，可以得到需要，BUILD-MAX-HEAP需要次呼叫，因此總時間複雜度為，雖然這是一個正確的上界，但卻不夠逼近函數。

我們可以試著求出更加逼近這個函數的上界。可以觀察到，執行MAX-HEAPIFY的時間與該節點的樹高有關，而且大部分的節點高度都比較小，這也是我們使用產生出不夠逼近的上界的原因，我們可以使用樹的性質去求出更精確地上界，含有個元素的heap高度為，高度為的heap最多有個節點

對於高度為的heap，MAX-HEAPIFY的時間複雜度為，因此，我們可以將BUILD-MAX-HEAP的時間代價以下面這個式子表示

而
於是，整個BUILD-MAX-HEAP的時間複雜度為

Heap sort

最一開始，Heap sort會呼叫BUILD-MAX-HEAP將輸入的陣列變成max heap。

因為陣列中最大元素總是在根節點，也就是中，我們把它和進行交換，並將從heap中去除，也就是彈出目前heap的最大節點，經過這樣的操作我們會發現原來根節點的子節點仍然會維持max heap，但是根節點可能會違反max heap的規則。

為了維持max heap，我們呼叫NAX-HEAPIFY(A, 1)，在上建造出新的max heap，直到heap的大小從下降到。

HEAPSORT(A)
BUILD-MAX-HEAP(A)
for i = A.length downto 2
    exchange A[1] with A[i]
    A.heap-size = A.heap-size - 1
    MAX-HEAPIFY(A, 1)

初始狀態，呼叫BUILD-MAX-HEAP建造出max heap

彈出heap中最大元素，並MAX-HEAPIFY










整個思路就是運用max heap的最大節點會在根節點的特性去完成排序。

heap sort的時間複雜度為，呼叫BUILD-MAX-HEAP的時間複雜度為，而呼叫了次MAX-HEAPIFY，每一次呼叫MAX-HEAPIFY的時間複雜度為，因此整個heap sort時間複雜度為。

實作 :

#include <iostream>
#include <algorithm>
using namespace std;

typedef struct object
{
    int array[11] = {-1, 16, 4, 10, 14, 7, 9, 3, 2, 8, 1};
    int heap_size = 10;
    int array_size = 10;
} object;
void max_heapify(object *, int);
void build_max_heap(object *);
void heap_sort(object *);
int parent(int);
int left_child(int);
int right_child(int);
int main(void)
{
    object A;
    heap_sort(&A);
    for (int i = 1; i < 11; i++)
    {
        cout << A.array[i] << ' ';
    }
}
int parent(int i)
{
    if (i == 0)
    {
        return 0;
    }
    return i / 2;
}

int left_child(int i)
{
    return 2 * i;
}

int right_child(int i)
{
    return (2 * i) + 1;
}

void max_heapify(struct object *A, int i)
{
    int l = left_child(i);
    int r = right_child(i);
    int largest = 0;
    if ((l <= A->heap_size) && (A->array[l] > A->array[i]))
    {
        largest = l;
    }
    else
    {
        largest = i;
    }
    if ((r <= A->heap_size) && (A->array[r] > A->array[largest]))
    {
        largest = r;
    }
    if (largest != i)
    {
        swap(A->array[i], A->array[largest]);
        max_heapify(A, largest);
    }
}

void build_max_heap(object *A)
{
    A->heap_size = A->array_size;
    for (int i = A->array_size / 2; i >= 1; i--)
    {
        max_heapify(A, i);
    }
}

void heap_sort(object *A)
{
    build_max_heap(A);
    for (int i = A->heap_size; i >= 2; i--)
    {
        swap(A->array[1], A->array[i]);
        A->heap_size = A->heap_size - 1;
        max_heapify(A, 1);
    }
}

(直到鐵人賽第10天，才知道自己記錯了書名...)
參考資料:Introduction to algorithms 3rd