堆的基本存储（Java 实例代码）

桃扇骨 2023-10-14 15:51 10阅读 0赞

##  ##

## 堆的基本存储 ##

#### 一、概念及其介绍 ####

堆(Heap)是计算机科学中一类特殊的数据结构的统称。

堆通常是一个可以被看做一棵完全二叉树的数组对象。

堆满足下列性质：

*  堆中某个节点的值总是不大于或不小于其父节点的值。
 *  堆总是一棵完全二叉树。

#### 二、适用说明 ####

堆是利用完全二叉树的结构来维护一组数据，然后进行相关操作，一般的操作进行一次的时间复杂度在 O(1)~O(logn) 之间，堆通常用于动态分配和释放程序所使用的对象。

若为优先队列的使用场景，普通数组或者顺序数组，最差情况为 O(n^2)，堆这种数据结构也可以提高入队和出队的效率。

#### 三、结构图示 ####

二叉堆是一颗完全二叉树，且堆中某个节点的值总是不大于其父节点的值，该完全二叉树的深度为 k，除第 k 层外，其它各层 (1～k-1) 的结点数都达到最大个数，第k 层所有的结点都连续集中在最左边。

其中堆的根节点最大称为最大堆，如下图所示：

![76ae0ed0e225c9a6370ee5abbb1e2154.png][]

我们可以使用数组存储二叉堆，右边的标号是数组的索引。

![1cbddf4a80a4df539fefe79859484f35.png][]

![051c541f92f77a4048831e9e5272948e.png][]

假设当前元素的索引位置为 i，可以得到规律：

parent(i) = i/2（取整）
    left child(i) = 2*i
    right child(i) = 2*i +1

#### 四、Java 实例代码 ####

**源码包下载：**[Download![icon-default.png?t=N6B9][icon-default.png_t_N6B9]https://www.runoob.com/wp-content/uploads/2020/09/runoob-algorithm-heap.zip][Download_icon-default.png_t_N6B9_icon-default.png_t_N6B9_https_www.runoob.com_wp-content_uploads_2020_09_runoob-algorithm-heap.zip]

### 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());  
\}  
\}

[76ae0ed0e225c9a6370ee5abbb1e2154.png]: https://img-blog.csdnimg.cn/img_convert/76ae0ed0e225c9a6370ee5abbb1e2154.png
[1cbddf4a80a4df539fefe79859484f35.png]: https://img-blog.csdnimg.cn/img_convert/1cbddf4a80a4df539fefe79859484f35.png
[051c541f92f77a4048831e9e5272948e.png]: https://img-blog.csdnimg.cn/img_convert/051c541f92f77a4048831e9e5272948e.png
[icon-default.png_t_N6B9]: https://csdnimg.cn/release/blog_editor_html/release2.3.5/ckeditor/plugins/CsdnLink/icons/icon-default.png?t=N6B9
[Download_icon-default.png_t_N6B9_icon-default.png_t_N6B9_https_www.runoob.com_wp-content_uploads_2020_09_runoob-algorithm-heap.zip]: https://www.runoob.com/wp-content/uploads/2020/09/runoob-algorithm-heap.zip