以前在学习堆时,写了两篇文章:数据结构--堆的实现(上) 和 数据结构--堆的实现(下), 感觉对堆的认识还是不够。本文主要分析数据结构 堆(讨论小顶堆)的基本操作的一些细节,比如 insert(插入)操作 和 deleteMin(删除堆顶元素)操作的实现细节、分析建堆的时间复杂度、堆的优缺点及二叉堆的不足。
二,堆的实现分析
堆的物理存储结构是一维数组,逻辑存储结构是完全二叉树。堆的基本操作有:insert--向堆中插入一个元素;deleteMin--删除堆顶元素
故堆的类结构如下:
public class BinaryHeap<T extends Comparable<? super T>> { private T[] array; private int currentSize; public BinaryHeap() { } public BinaryHeap(T[] array){ } public void insert(T x){ //do something } public T deleteMin(){ } //other operations.... }