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

  本篇文章为你整理了大顶堆的实现(基于数组存储的完全二叉树)(大顶堆和二叉排序树)的详细内容,包含有大顶堆数组形式 大顶堆和二叉排序树 大顶堆序列 大顶堆算法 大顶堆的实现(基于数组存储的完全二叉树),希望能帮助你了解 大顶堆的实现(基于数组存储的完全二叉树)。

  满二叉树
 

  
 

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

  
 

  完全二叉树
 

  完全二叉树的特点

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

  完全二叉树的实现

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

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

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

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

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

  则:

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

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

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

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

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

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

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

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

  堆的插入流程如下:

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

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

  重复步骤 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)

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

  堆的删除流程如下:

  取出堆顶的数据

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

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

  重复步骤 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

   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;

  

 

  以上就是大顶堆的实现(基于数组存储的完全二叉树)(大顶堆和二叉排序树)的详细内容,想要了解更多 大顶堆的实现(基于数组存储的完全二叉树)的内容,请持续关注盛行IT软件开发工作室。

郑重声明:本文由网友发布,不代表盛行IT的观点,版权归原作者所有,仅为传播更多信息之目的,如有侵权请联系,我们将第一时间修改或删除,多谢。

留言与评论(共有 条评论)
   
验证码: