现在的位置: 首页 > 面试题 > 正文

堆的基本存储

2022年01月10日 面试题 ⁄ 共 985字 ⁄ 字号 暂无评论
博客主机

一、概念及其介绍

堆(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/runoob/heap/MaxHeap.java 文件代码:

package runoob.heap;

 

/**

* 堆定义

*/

public class MaxHeap<T> {

private T[] data;

private int count;

// 构造函数, 构造一个空堆, 可容纳capacity个元素

public MaxHeap(int capacity){

data = (T[])new Object[capacity+1];

count = 0;

}

// 返回堆中的元素个数

public int size(){

return count;

}

// 返回一个布尔值, 表示堆中是否为空

public boolean isEmpty(){

return count == 0;

}

// 测试 MaxHeap

public static void main(String[] args) {

MaxHeap<Integer> maxHeap = new MaxHeap<Integer>(100);

System.out.println(maxHeap.size());

}

}

Wopus问答

【上篇】
【下篇】

Wopus问答

给我留言

留言无头像?


×