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