Day-10 heap与heap sort

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