大顶堆的实现

 

小（大）顶堆的实现

 

 

1. 用数组表示二叉树

 

二叉树表示如下图:

 

 

用数组表示二叉树

2	3	4	6	8
A0	A1	A2	A3	A4

 

大顶堆特性

1. 子节点大于（小于）父节点

2. 如果父节点为n，左子节点为2n+1，右子节点为2n+2

3. 如果该节点为n，其父节点为(n-1)/2

 

压栈：

1.在数组的最末尾插入数据，满足二叉树的特性

2.将新插入节点到顶点间路径的节点排序，满足大顶堆的特性

 

 

 

弹出：

1.将数组最后一项和数组第一项交换，弹出数组最后一项

2.将数组第一项下沉到某一特定层数。

 

插入和删除都是O（lgN）