数据结构--堆的实现之深入分析

以前在学习堆时,写了两篇文章:数据结构--堆的实现(上)   和   数据结构--堆的实现(下),  感觉对堆的认识还是不够。本文主要分析数据结构 堆(讨论小顶堆)的基本操作的一些细节,比如 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.... }

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/zgzdpf.html