堆和二叉堆

编程入门行业动态更新时间:2024-10-16 18:25:20

堆和<a href=https://www.elefans.com/category/jswz/34/1769947.html style= 二叉堆"/>

堆和二叉堆

文章目录

- 一、堆和二叉堆
- - 1.1 什么是堆
  - 1.2 堆的类型
  - 1.3 二叉堆
  - 1.4 堆的声明
  - 1.5 堆化元素
  - 1.6 删除元素
  - 1.7 插入元素
  - 1.8 清空堆
  - 1.9 数组建堆
  - 1.10 堆排序
- 二、堆的相关问题
- - 2.1 是否存在一个包含7个不同元素的最小堆，其前序遍历是有序的？
  - 2.2 是否存在一个包含7个不同元素的最大堆，其前序遍历序列是否是有序的
  - 2.3 是否存在一个包含7个不同数据的最小/大堆，其中序遍历序列是有序的
  - 2.3 是否存在一个包含7个不同数据的最小/大堆，其后序遍历序列是有序的
- 参考

一、堆和二叉堆

1.1 什么是堆

堆是一棵具有特定性质的二叉树。堆的基本要求是堆中所有结点的值必须大于或等于(或小于或等于)其孩子结点的值。除此以外，所有叶子结点都是处于第 h 或 h - 1层（h为树的高度），其实堆也是一个完全二叉树。

1.2 堆的类型

最小堆： 结点的值必须小于或等于其孩子结点的值

最大堆： 结点的值必须大于或等于其孩子结点的值

1.3 二叉堆

在二叉堆中，每个结点最多有两个孩子结点。

堆的表示： 堆在形式上是一棵完全二叉树，用数组来存储不会浪费空间。下面讨论假定所有元素都存储在数组中，从下标 0 开始。上述最大堆可以表示如下：

1.4 堆的声明

public class Heap {private int[] array;private int count; //堆中元素个数private int capacity;//对的大小private int heap_type; //标记：最大堆还是最小堆/*** 创建堆* @param capacity* @param heap_type*/public Heap(int capacity, int heap_type) {this.capacity = capacity;this.heap_type = heap_type;this.count = 0;this.array = new int[capacity];}/*** 对应第i个位置上的结点，其双亲结点在（i-1）/2 位置上* @param i* @return*/public int parent(int i) {if(i <=0 || i >= this.count) {return -1;}return (i - 1) / 2 ;}/*** 第i个位置结点的孩子处在 2 * i + 1 和 2 * i + 2 位置上* @param i* @return*/public int leftChild(int i) {int left = 2 * i + 1;if(left >= this.count) {return -1;}return left;}public int rightChild(int i) {int right = 2 * i + 2;if(right >= this.count) {return -1;}return right;}/*** 最大堆中的最大元素总是根节点，* 所以它存储在数组的 0 号位置* @return*/public int getMaximum() {if(this.count == 0) {return -1;}return this.array[0];}
}

1.5 堆化元素

当插入一个元素到堆中时，它可能不满足堆的性质。这种情况下，需要调整整堆中元素的位置使之重新变为堆，这个过程叫做堆化。

在最大堆中，要堆化一个元素，需要找到它的孩子结点中的最大值，然后将它与当前元素交换，重复该过程直至每个结点都满足堆的性质为止。

堆的一个重要性质，如果一个元素不满足堆的性质，那么从这个元素开始到根节点的所有元素都存在这个问题。在下图所示的例子中，元素1不满足堆的性质，它的父节点31也同样不满足。类似地，如果堆化该元素，那么从这个元素到根节点的所有元素都自动满足堆的性质。

为了堆化1 ，先找到它孩子结点中的最大值，然后交换它们的位置。

需要持续这个过程，直到元素都满足堆的性质。

该过程是自顶向下移动，所以这个过程又叫做向下渗透

code 如下，仅做参考：

/*** 堆化当前元素，时间复杂度O(logn)* @param i*/
public void percolateDown(int i) {int l,r,max,temp;l = leftChild(i);r = rightChild(i);if(l != -1 && this.array[l] > this.array[i]) {max = l;} else {max = i;}if(r != -1 && this.array[r] > this.array[max]) {max = r;  } if(max != i) {temp = this.array[i];this.array[i] = this.array[max];this.array[max] = temp;}percolateDown(max);
}

1.6 删除元素

为了删除堆中元素，只需要从根结点删除元素（这时标准堆支持的唯一操作,即最大元素）。当删除根结点后，将堆的最后一个元素复制到这个位置，然后删除最后的元素。当用最后元素替换树的根结点后，可能导致树不满足堆的性质。为使其再次成为堆，需要调用函数percolateDown。

/*** 时间复杂度 O(logn)* @return*/
public int deleteMax() {if(this.count == 0) {return -1;}int data = this.array[0];this.array[0] = this.array[this.count-1];this.count--; //减小堆的大小，不访问最后一个元素。percolateDown(0);return data;
}

1.7 插入元素

插入元素类似于堆化和删除过程

堆大小加1
将新元素放在堆的尾部
从上至下堆化这个元素（从根结点开始）

例如：下图所示，在堆的尾部插入元素 19，这就使得树不再满足堆的性质。

为了堆化元素19，需要将它与它的双亲大小进行比较，并调整它们。交换19和14。

交换19 和 16

现在该树满足堆的性质，这种方法从下至上比较和调整元素，所以也将这种方法叫做向上渗透

public int insert(int data) {int i;if(this.count == this.capacity) {resizeHeap();}this.count++;i = this.count - 1;while (i >= 0 && data > this.array[(i-1)/2]) {this.array[i] = this.array[(i-1)/2];i = (i-1)/2;}this.array[i] = data;return i;
}private void resizeHeap() {int[] array_old = new int[this.capacity];System.arraycopy(this.array,0,array_old,0,this.count-1);this.array = new int[this.capacity * 2];for(int i = 0; i < this.capacity; i++) {this.array[i] = array_old[i];}this.capacity = this.capacity * 2;array_old = null;
}

1.8 清空堆

 public void destoryHeap() {this.count = 0;this.array= null;}

1.9 数组建堆

创建堆的一个简单方法是，取n个输入数据，然后将它们插入空堆中。

叶子结点总是满足堆的性质，不需要关注它们，叶子结点元素总是在最后面，因此要对给定的数组建堆，只要堆化非叶子结点即可。堆的最后一个元素所处的位置为 i = count-1。通过最后元素的双亲结点就能找到第一个非叶子结点

 public void buildHeap(Heap h,int arr[],int capacity) {if(h == null) {return;}while (capacity > this.capacity) {h.resizeHeap();}for (int i = 0; i < capacity; i++) {h.array[i] = arr[i];}for(int i = (capacity-1)/2; i >=0;i--) {h.percolateDown(i);}}

1.10 堆排序

public void heapSort(int arr[],int capacity) {Heap h = new Heap(capacity,0);int old_siz,i,temp;buildHeap(h,arr,capacity);old_siz = h.count;for(i = capacity - 1; i > 0; i--) {//h.array[0]存储最大元素temp = h.array[0];h.count--;h.percolateDown(i);}h.count = old_siz;
}