堆的数据结构和相关性质

逻辑结构为一个近似完全二叉树，具有完全二叉树的性质

物理结构为数组

A.length为数组中元素的个数

A.heap-size为存放在数组A中的堆的元素个数

A.length≥A.heap-size

对于某二叉树中的节点i，对应到数组A中的索引位置：

1. i的父节点为⌊i/2⌋（向下取整）
2. i的左子节点为2i
3. i的右子节点为2i+1

注意：这里的乘除2的操作在实际代码中可以使用左移右移操作来提高效率

最大堆：A[PARENT(i)]≥A[i]
最小堆：A[PARENT(i)]≤A[i]

只能保证树根是最大的或最小的！！！

最大堆

MAX-HEAPIFY

维护最大堆的性质

输入为数组A和下标i，以及堆的元素个数A.heap-size

一个很重要的假定：假定根节点为LEFT(i)和RIGHT(i)的二叉树都是最大堆。即对于i来讲，它的左右子树已经都是最大堆了。

伪代码：

/**
MAX-HEAPIFY
*/

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[i]
	largest = r
	
if largest != i
	exchange A[i] with A[largest]
	MAX-HEAPIFY(A, largest)

对于一个数高为h的节点来说，MAX-HEAPIFY的时间复杂度为O(h)

BUILD-MAX-HEAP

建堆

对于大小为n的数组A[1..n]来说，子数组A(⌊n/2⌋+1..n)中的元素都是树的叶子节点

输入一个数组A

伪代码：

/**
BUILD-MAX-HEAP
*/

A.heap-size = A.length

for i = ⌊A.length/2⌋ downto 1
	MAX-HEAPIFY(A, i)

时间复杂度为O(n)，即可以在线性时间内讲一个无序数组构造成一个最大堆

HEAPSORT

伪代码：

/**
HEAPSORT
*/

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

MAX-HEAP-INSERT

HEAP-EXTRACT-MAX

HEAP-INCREASE-KEY

HEAP-MAXIMUM

最小堆

MIN-HEAPIFY

BUILD-MINHEAP

HEAPSORT

MIN-HEAP-INSERT

HEAP-EXTRACT-MIN

HEAP-DECREASE-KEY

HEAP-MINIMUM