定义

1.是一个二叉树

2.是满二叉树，但是如果多出来元素，必须在最后一层左侧依次开始填充

3.任意一个结点到叶子结点，必须是递减（max heap）或者递增（min heap）的，

性质

1.堆可以用一个数组来存储，用level order遍历后存放。

第0个元素是空的，然后按照1+2+4+…的方式存放

0	1	2	3	4	5	6	…
空	A	B	C	D	E	F	…

2.对于第i个元素

父节点是i/2

左孩子是i*2

右孩子是i*2+1

3.堆顶是最大或者最小的元素

操作

1.插入元素

插入到最后一层最左侧的位置，然后沿着父节点的路径往上换就可以了

实际操作的时候是往后挪，挪到了以后加上去，复杂度O(logn)

void  Insert( ElementType  X,  PriorityQueue  H ) 
{ 
     int  i; 

     if ( IsFull( H ) ) 
     { 
		Error( "Priority queue is full" ); 
		return; 
     } 
	/*首先确定初始位置是堆的个数+1，这个位置到根的路径是i/2*/
     for ( i = ++H->Size; H->Elements[ i / 2 ] > X; i /= 2 ) 
		H->Elements[ i ] = H->Elements[ i / 2 ]; 
		/*当第(i/2)个大于X的时候，就往后移动，i/2小于X的时候，就让孩子i变成X*/
		
     H->Elements[ i ] = X; //
}

2.删除堆顶元素(shift down)

相当于把堆的最后一个元素放在堆顶，然后顺着一条路往下换。

注意由于往上换只可能是一条路，但是往下换有两个孩子，应该将最小的放在父节点的位置，所以说将child指向小的子结点，再和父节点比较。

ElementType  DeleteMin( PriorityQueue  H ) 
{ 
    int  i, Child; 
    ElementType  MinElement, LastElement; 
    if ( IsEmpty( H ) ) 
    { 
         Error( "Priority queue is empty" ); 
         return  H->Elements[ 0 ];   
    } 
    MinElement = H->Elements[ 1 ];  /* save the min element */
    LastElement = H->Elements[ H->Size-- ];  /* take last and reset size */
    for ( i = 1; i * 2 <= H->Size; i = Child ) 
    {  /* Find smaller child */ 
         Child = i * 2; 
         if (Child != H->Size && H->Elements[Child+1] < H->Elements[Child]) 
	       Child++;     /*如果child+1更小，让child指向child+1*/
         if ( LastElement > H->Elements[ Child ] )   /* Percolate one level */ 
	     	H->Elements[ i ] = H->Elements[ Child ]; /*把child放在i的位置，和最后一句对应*/
         else
         	break;   /* find the proper position */
    } 
    H->Elements[ i ] = LastElement; /*把本来的最后一个元素放在i的位置，和上面那句对应*/
    return  MinElement; 
}

3.建堆

(1)首先把数组按照层序（level order）放在一个空堆中
(2)从最后一个父节点开始，让父节点，右孩子，左孩子中最小的放在父节点的位置。
(3)如果父节点被换下去了，那么必须执行shiftdown操作，即被换下去的结点与当前的子节点比较，并交换，直到符合比任何一个子节点大的条件。

for(i = N/2; i > 0; i--)
	PrecolateDown(i);

4.找到第k大的数

删掉最小的，删k次，复杂度为$O(d{\log }_{d}k)$

d是d叉树，即最大degree

总结

1.只对最后一个位置操作，插入则插在最后一个位置的后一个，再往上换。删除则将最后一个元素放在要删的位置，然后往下换（因为最后一个元素应该是大于被删的）

2.往上换，只与父节点比较，往下换，则需要和两个孩子都比较，必须找三个中最小的放进去。

题目

1.The number of leaf nodes in a complete binary tree with 124 nodes is definite

堆（完全二叉树多余的叶子只能从最后一层最左边开始加，因此是确定的）

2.In a max-heap with n (>1) elements, the array index of the minimum key may be __.

A.1 B.⌊n/2⌋−1 C.⌊n/2⌋ D.⌊n/2⌋+2

最小的元素一定是叶子结点中的一个，n/2是最后一个结点的上一层，如果父节点在最右边，n/2+2可能到下一层，因此可能是最小的，其他的都是父节点同层的，因此不可能。

3.Using the linear algorithm to build a min-heap from the sequence {15, 26, 32, 8, 7, 20, 12, 13, 5, 19}, and then insert 6. Which one of the following statements is FALSE?

建堆注意是将序列写做堆的样子，然后从第一个父节点开始执行往下换的操作，不是一个一个插入。
对7shiftdown:不变
对8shiftdown:15 26 32 5 7 20 12 13 8 19
对32shiftdown:15 26 12 5 7 20 32 13 8 19
对26shiftdown:15 5 12 8 7 20 32 13 26 19
对15shiftdown: 5 7 12 8 15 20 32 13 26 19
插入6: 6 12 8 7 20 32 13 20 19 15

4.The result of performing three DeleteMin operations in the min-heap {1,3,2,12,6,4,8,15,14,9,7,5,11,13,10} is:
(5分)
A.4,5,6,12,7,10,8,15,14,13,9,11
B.4,5,6,7,8,9,10,11,12,13,14,15
C.4,6,5,12,7,10,8,15,14,9,13,11
D.4,6,5,13,7,10,8,15,14,12,9,11

删除，就是把堆尾的放在堆顶，然后shiftdown，执行三次，选C