堆的基本存储
一、概念及其介绍
堆(Heap)是计算机科学中一类特殊的数据结构的统称。
堆通常是一个可以被看做一棵完全二叉树的数组对象。
堆满足下列性质：
- 堆中某个节点的值总是不大于或不小于其父节点的值。
- 堆总是一棵完全二叉树。
二、适用说明
堆是利用完全二叉树的结构来维护一组数据，然后进行相关操作，一般的操作进行一次的时间复杂度在 O(1)~O(logn) 之间，堆通常用于动态分配和释放程序所使用的对象。
若为优先队列的使用场景，普通数组或者顺序数组，最差情况为 O(n^2) ，堆这种数据结构也可以提高入队和出队的效率。
| 入队 | 出队 | |
|---|---|---|
| 普通数组 | O(1) | O(n) |
| 顺序数组 | O(n) | O(1) |
| 堆 | O(logn) | O(log) |
三、结构图示
二叉堆是一颗完全二叉树，且堆中某个节点的值总是不大于其父节点的值，该完全二叉树的深度为 k，除第 k 层外，其它各层 (1～k-1) 的结点数都达到最大个数，第k 层所有的结点都连续集中在最左边。
其中堆的根节点最大称为最大堆，如下图所示：
我们可以使用数组存储二叉堆，右边的标号是数组的索引。
假设当前元素的索引位置为 i，可以得到规律：
parent(i) = i/2（取整） left child(i) = 2*i right child(i) = 2*i +1
四、Java 实例代码
源码包下载： Download
src/yssmx/heap/MaxHeap.java 文件代码：
/**
* 堆定义
*/
public class MaxHeap < T > {
private T [ ] data ;
private int count ;
// 构造函数, 构造一个空堆, 可容纳capacity个元素
public MaxHeap ( int capacity ) {
data = ( T [ ] ) new Object [ capacity + 1 ] ;
count = ;
}
// 返回堆中的元素个数
public int size ( ) {
return count ;
}
// 返回一个布尔值, 表示堆中是否为空
public boolean isEmpty ( ) {
return count == ;
}
// 测试 MaxHeap
public static void main ( String [ ] args ) {
MaxHeap < Integer > maxHeap = new MaxHeap < Integer > ( 100 ) ;
System . out . println ( maxHeap. size ( ) ) ;
}
}
