堆是一种完全二叉树（每个结点最多有两个子节点，且结点总是有限从最左边排列）。下图是一个最大堆（父节点总是比子节点大）。

需要注意的是左右两个子节点之间并没有确定的大小关系。

最大堆

由于堆的定义，堆具有如下性质：

位置为k的节点孩子节点位置为2k, 2k+1；
位置为k的节点的父节点位置为[2/k]向下取整。

所以堆可以使用数组来存储。为了计算方便，一般把数组的第一个位置下标0空出来，从下标1开始放堆的元素。

/**
 * 堆接口
 */
public interface IHeap {
    int size(); // 当前元素的长度
    boolean isEmpty(); // 判空
    void add(T data); // 添加
    T pop(); // 弹出堆顶元素
    T remove(int i); // 移除某位置元素
    T peek(); // 过去堆顶元素
}

代码地址

测试代码

ITPub博客

数据结构——堆

最新文章