写点什么

大顶堆的实现(基于数组存储的完全二叉树)

作者:Java你猿哥
  • 2023-03-23
    湖南
  • 本文字数:3663 字

    阅读完需:约 12 分钟

完全二叉树

完全二叉树的定义

满二叉树


非完全二叉树,非满二叉树


完全二叉树


完全二叉树的特点

叶子结点只能出现在最下层和次下层,且最下层的叶子结点集中在树的左部。

完全二叉树的实现

  • 二叉链表:直观,但占用内存大。

  • 数组:简洁,但拓展麻烦。

比较推荐使用数组存储,本文也将基于数组存储介绍大顶堆的实现。

基于数组存储的完全二叉树节点与数组下标的关系

假设完全二叉树的 节点 A 存储在数组中的下标为 i 则:

  • 节点 A 的 父节点 存储在数组中的下标为 (i - 1) / 2

  • 节点 A 的 电子节点 存储在数组中的下标为 2 * i + 1

  • 节点 A 的 右子节点 存储在数组中的下标为 2 * i + 2


堆的定义

堆是一种特殊的数据结构,是高效的优先级队列,堆通常可以被看做一棵完全二叉树。

堆的分类

根据堆的特点,可以把堆分为两类:

  • 大顶堆:每一个节点的值都大于或等于其左右子节点的值。

  • 小顶堆:每一个节点的值都小于或等于其左右子节点的值。

堆的插入

往堆中插入数据,可能会破坏大顶堆(小顶堆)的性质,需要对堆进行调整。

堆的插入流程如下:

  1. 将插入的数据置于数组的尾部

  2. 将新插入的节点作为当前节点,比较当前节点与其父节点是否满足堆的性质,不满足则交换

  3. 重复步骤 2,直到满足堆的性质或者当前节点到达堆顶。


/** * 添加元素 * @param value 待添加元素 */public void offer(int value){  if(this.currentLength >= this.capacity){    // 数组已耗尽,扩增数组为原来的两倍    this.grow();  }  int cur = this.currentLength++;             // 获得待添加元素的添加位置  if(cur == 0){                               // 当前堆为空直接添加    this.tree[cur] = value;  }else{                                      // 当前堆不为空,添加之后要向上调整    this.tree[cur] = value;                   // 步骤 1    int p = cur;                                int parent = this.getParentIndex(p);        while(this.tree[parent] < this.tree[p]){  // 步骤 2      this.swap(parent, p);      p = parent;      parent = this.getParentIndex(p);    }  }}
复制代码

往堆中插入数据的时间复杂度为 O(logN)

堆的构建

构建一个大小为 N 地堆,其实就是执行 N 次插入。

所以构建一个大小为 N 的堆,其时间复杂度为 O(NlogN)

堆的删除

堆的删除也可能会破坏大顶堆(小顶堆)的性质,需要对堆进行调整。

堆的删除流程如下:

  1. 取出堆顶的数据

  2. 用堆的最后一个元素代替堆顶元素

  3. 判断当前节点(一开始是堆顶),是否满足大顶堆(小顶堆)的性质,不满足则用左右子节点中较大的节点进行交换

  4. 重复步骤 3 直到满足堆的性质或没有子节点


/** * 取出最大元素 * @return 最大元素 */public int poll(){    if(isEmpty()){        throw new RuntimeException("堆为空,无法取出更多元素!");    }    int cur = --this.currentLength;         // 获得当前堆尾    int result = this.tree[0];              // 取出最大元素 步骤1    this.tree[0] = this.tree[cur];          // 将堆尾移到堆头 步骤2    if(cur != 0){                           // 如果取出的不是最后一个元素,需要向下调整堆 步骤3        int p = 0;        int left = getLeftIndex(p);        int right = getRightIndex(p);        // 由于是数组实现,数组元素无法擦除,需要通过边界进行判断堆的范围        // 当前节点和左节点在堆的范围内,        while(p < this.currentLength &&                0 <= left && left < this.currentLength &&                (this.tree[left] > this.tree[p] || this.tree[right] > this.tree[p])){            if(right >= this.currentLength){    // 当前节点没有右节点                if(this.tree[left] > this.tree[p] ){        // 左节点大于当前节点                    swap(p, left);                    p = left;                }            }else{                                          // 两个节点都在堆范围                if(this.tree[left] > this.tree[right]){     // 用大的节点替换                    swap(p, left);                    p = left;                }else{                    swap(p, right);                    p = right;                }            }            left = getLeftIndex(p);            right = getRightIndex(p);        }    }    return result;}
复制代码

堆的删除元素时间复杂度为 O(logN)

完整代码

// 大顶堆public class Heap {    private int[] tree;         // 数组实现的完全二叉树    private int capacity;       // 容量    private int currentLength;  // 当前数组已使用长度
/** * 构造函数 * @param capacity 初始容量 */ public Heap(int capacity) { this.tree = new int[capacity]; this.capacity = capacity; this.currentLength = 0; }
/** * 添加元素 * @param value 待添加元素 */ public void offer(int value){ if(this.currentLength >= this.capacity){ // 数组已耗尽,扩增数组为原来的两倍 this.grow(); } int cur = this.currentLength++; // 获得待添加元素的添加位置 if(cur == 0){ // 当前堆为空直接添加 this.tree[cur] = value; }else{ // 当前堆不为空,添加之后要向上调整 this.tree[cur] = value; // 步骤 1 int p = cur; int parent = this.getParentIndex(p); while(this.tree[parent] < this.tree[p]){ // 步骤 2 this.swap(parent, p); p = parent; parent = this.getParentIndex(p); } } }
/** * 取出最大元素 * @return 最大元素 */ public int poll(){ if(isEmpty()){ throw new RuntimeException("堆为空,无法取出更多元素!"); } int cur = --this.currentLength; // 获得当前堆尾 int result = this.tree[0]; // 取出最大元素 步骤1 this.tree[0] = this.tree[cur]; // 将堆尾移到堆头 步骤2 if(cur != 0){ // 如果取出的不是最后一个元素,需要向下调整堆 步骤3 int p = 0; int left = getLeftIndex(p); int right = getRightIndex(p); // 由于是数组实现,数组元素无法擦除,需要通过边界进行判断堆的范围 // 当前节点和左节点在堆的范围内, while(p < this.currentLength && 0 <= left && left < this.currentLength && (this.tree[left] > this.tree[p] || this.tree[right] > this.tree[p])){ if(right >= this.currentLength){ // 当前节点没有右节点 if(this.tree[left] > this.tree[p] ){ // 左节点大于当前节点 swap(p, left); p = left; } }else{ // 两个节点都在堆范围 if(this.tree[left] > this.tree[right]){ // 用大的节点替换 swap(p, left); p = left; }else{ swap(p, right); p = right; } } left = getLeftIndex(p); right = getRightIndex(p); } } return result; }
public boolean isEmpty(){ return this.currentLength <= 0; }
private int getParentIndex(int index){ return (index - 1) / 2; }
private int getLeftIndex(int index){ return 2 * index + 1; }
private int getRightIndex(int index){ return 2 * index + 2; }
private void swap(int left, int right){ int temp = this.tree[left]; this.tree[left] = this.tree[right]; this.tree[right] = temp; }
/** * 将数组拓展为原来的两倍 */ private void grow(){ this.tree = Arrays.copyOf(this.tree, 2 * currentLength); this.capacity = this.tree.length; }}
复制代码


用户头像

Java你猿哥

关注

一只在编程路上渐行渐远的程序猿 2023-03-09 加入

关注我,了解更多Java、架构、Spring等知识

评论

发布
暂无评论
大顶堆的实现(基于数组存储的完全二叉树)_Java_Java你猿哥_InfoQ写作社区