教你做网站,wordpress教学,网站建设准备工作,健身餐的网站怎么做一、完全二叉树
堆是一种完全二叉树#xff0c;什么是完全二叉树#xff1f;
简单的说#xff0c;一棵满二叉树表示的是所有节点全部饱和#xff0c;最后一层全部占满#xff1a; 而完全二叉树指的是满二叉树的最后一层#xff0c;所有叶子节点都从左往顺序排满#x…一、完全二叉树
堆是一种完全二叉树什么是完全二叉树
简单的说一棵满二叉树表示的是所有节点全部饱和最后一层全部占满 而完全二叉树指的是满二叉树的最后一层所有叶子节点都从左往顺序排满 完全二叉树的特点非常简单除了最后一层其他各层节点都是满的而最后一层所有节点从左往右依次排满。它并不关心节点元素的大小只与这一结构特点有关。
二、堆结构
前面说到堆是一种特殊的完全二叉树除了符合完全二叉树的结构特点它还有另一个特性由这个特性我们又可以将堆分为——大根堆、小根堆。
大根堆每个节点比它的子节都要大。
小根堆和大根堆相反每个节点比它的子节点都要小。 注意堆只关心父节点与子节点之间的大小要么父节点比子节点都大视为大根堆要么父节点比子节点都小视为小根堆。只要保证这一点再加上完全二叉树的特点就是一个堆结构。至于全部节点是否呈现一种左大右小或左小右大的关系堆并不关心。 如何实现一个堆
堆并不是一个实际存在的物理结构它需要通过一个一维数组来表示。实际上数组表示了堆的一种对应关系。 有了这样一种对应关系我们可以得到下面 3 个公式 已知任意位置 index求其父节点和子节点位置 父节点int fatherIdx (index - 1) / 2; // 注意 (0 - 1) / 2 0实际上double-int 是向0取整或绝对值向下取整。 左子节点int leftIdx index * 2 1; 右子节点int rightIdx index * 2 2; 例如4 位置的父节点是 1 位置(4 - 1) / 2 1 向下取整。
有了位置关系剩下的工作就是实现大根堆或小根堆一般情况大根堆可以快速返回整个堆中的最大值比较常用以下就以大根堆为例。
接下来我们通过代码来详细解析如何实现一个堆结构。
三、堆结构的实现
以数组为基础构建一个大根堆的对应关系。这个堆结构需要实现以下几个公共方法 push 入堆pop 出堆isEmpty 是否为空isFull 是否已满实现堆结构的过程要始终紧扣两个特点 完全二叉树的特点大根堆的特点只有这两点满足它才是一个正确的堆。
当push一个元素的时候由于实现结构是数组因此始终是追加到数组的末尾但我们可以通过特定的方法来实现“堆结构”的调整。
想象这个元素被追加到了堆结构最后一层的末尾首先完全二叉树的条件就满足了。
但是大根堆的特点呢这时就需要从末尾开始向上与父节点比大小大的站在父节点的位置然后重复这个过程直到这个元素不再比父节点大或已经站在了 0 的位置。 public void push(int value) {if (isFull())throw new RuntimeException(heap is full);heap[heapSize] value;heapInsert(heap, heapSize);}private void heapInsert(int[] arr, int index) {// 当前位置元素比父节点大交换位置重置当前位置// 循环条件有两点作用1、当前节点父节点明显// 2、由于 (0-1)/20如果index已经是0位置出现相等的情况跳出循环隐藏while (arr[index] arr[(index - 1) / 2]) {SortUtil.swap(arr, index, (index - 1) / 2);index (index - 1) / 2;}}
而如果 pop 一个元素稍微复杂一些首先我们需要记录下 0 位置上的元素然后用堆的最后一个元素补位heapSize 缩减 1 位这几步操作是为了保证取出元素后依然是一个完全二叉树。
然后我们需要从 0 位置上已经替换为最后一个位置上的数与子节点比较找到最大的子节点然后与其交换下沉循环直到下沉到“堆的最后一层”或子节点都比自己小终止条件 public int pop() {int max heap[0];// 1、要拿掉根节点因为要保证是一个完全二叉树所以第一步我们取最后一个元素补位SortUtil.swap(heap, 0, heapSize - 1);// 2、heapSize缩减一位heapSize--;// 2、再执行heapify下沉操作因为补位的元素可能不满足大根的特点所以要向下比较heapify(heap, 0, heapSize);return max;}private void heapify(int[] arr, int i, int heapSize) {int left 2 * i 1;// 若左孩子没有越界证明存在下一级有可能需要下沉while (left heapSize) {// 选出子节点中最大的那个位置int largest left 1 heapSize arr[left] arr[left 1] ? left 1 : left;largest arr[largest] arr[i] ? largest : i;if (largest i)break;else {// 执行交换SortUtil.swap(arr, largest, i);i largest;left 2 * i 1;}}}
以下是完整代码
/*** 大根堆** data 2021/5/15 16:46*/
public class Code2_MaxHeap {/*** 堆容器*/private int[] heap;/*** 元素限制*/private final int limit;/*** 堆大小*/private int heapSize;public Code2_MaxHeap(int limit) {this.heap new int[limit];this.limit limit;this.heapSize 0;}public void push(int value) {if (isFull())throw new RuntimeException(heap is full);heap[heapSize] value;heapInsert(heap, heapSize);}/*** 1、因为是数组表示的堆结构每次插入都是在末尾因此index每次都是堆的最后一个值* 2、利用堆结构的特点可以快速求出当前位置的父节点在数组中的下标即(index - 1)/2* 3、比较当前位置与父节点 大小如果比父大交换然后当前位置变为父节点位置* 4、重复 2、3继续向上比较要么直到没有父节点那么while的条件会在两数相等时退出要么不比父节点大也停止向上比较。*/private void heapInsert(int[] arr, int index) {// 当前位置元素比父节点大交换位置重置当前位置while (arr[index] arr[(index - 1) / 2]) {SortUtil.swap(arr, index, (index - 1) / 2);index (index - 1) / 2;}}public int pop() {int max heap[0];// 1、要拿掉根节点因为要保证是一个完全二叉树所以第一步我们取最后一个元素补位SortUtil.swap(heap, 0, heapSize - 1);// 2、heapSize缩减一位heapSize--;// 2、再执行heapify下沉操作因为补位的元素可能不满足大根的特点所以要向下比较heapify(heap, 0, heapSize);return max;}private void heapify(int[] arr, int i, int heapSize) {int left 2 * i 1;// 若左孩子没有越界证明存在下一级有可能需要下沉while (left heapSize) {// 选出子节点中最大的那个位置int largest left 1 heapSize arr[left] arr[left 1] ? left 1 : left;largest arr[largest] arr[i] ? largest : i;if (largest i)break;else {// 执行交换SortUtil.swap(arr, largest, i);i largest;left 2 * i 1;}}}public boolean isEmpty() {return heapSize 0;}public boolean isFull() {return heapSize heap.length;}}
测试代码 public static void main(String[] args) {int value 1000;int limit 100;int testTimes 1000000;for (int i 0; i testTimes; i) {int curLimit (int) (Math.random() * limit) 1;Code2_MaxHeap my new Code2_MaxHeap(curLimit);RightMaxHeap test new RightMaxHeap(curLimit);int curOpTimes (int) (Math.random() * limit);for (int j 0; j curOpTimes; j) {if (my.isEmpty() ! test.isEmpty()) {System.out.println(Oops!);}if (my.isFull() ! test.isFull()) {System.out.println(Oops!);}if (my.isEmpty()) {int curValue (int) (Math.random() * value);my.push(curValue);test.push(curValue);} else if (my.isFull()) {if (my.pop() ! test.pop()) {System.out.println(Oops!);}} else {if (Math.random() 0.5) {int curValue (int) (Math.random() * value);my.push(curValue);test.push(curValue);} else {if (my.pop() ! test.pop()) {System.out.println(Oops!);}}}}}System.out.println(finish!);}/*** 遍历数组选出一个最大值 pop* 用于验证与自定义MaxHeap.pop的值是相等的。*/
class RightMaxHeap {private int[] arr;private final int limit;private int size;public RightMaxHeap(int limit) {arr new int[limit];this.limit limit;size 0;}public boolean isEmpty() {return size 0;}public boolean isFull() {return size limit;}public void push(int value) {if (size limit) {throw new RuntimeException(heap is full);}arr[size] value;}public int pop() {int maxIndex 0;for (int i 1; i size; i) {if (arr[i] arr[maxIndex]) {maxIndex i;}}int ans arr[maxIndex];arr[maxIndex] arr[--size];return ans;}
} 如果一个堆的某个位置的数变了还不知道变大还是变小如何重新调整堆结构 这个位置 i 顺序调用一下 heapinsert 和 heapify 整个堆就会自动整理好。 四、优先级队列与堆
java.util.PriorityQueueT 是一个优先级队列数据结构它的底层实现就是用堆来完成的。另外它是允许添加重复元素的这与 TreeMap 不允许添加重复元素有区别。
这种结构可以立刻返回最大值或最小值指定一个比较器参考《比较器的使用》符合“正减升反减降”的口诀。如果是按升序设定比较器那么 peek 或 poll 方法就会返回最小值。反之就是最大值。 public static void main(String[] args) {// 小根堆PriorityQueueInteger heap new PriorityQueue((o1, o2) - o1 - o2);heap.add(5);heap.add(5);heap.add(5);heap.add(3);// 5 , 3System.out.println(heap.peek());heap.add(7);heap.add(0);heap.add(7);heap.add(0);heap.add(7);heap.add(0);System.out.println(heap.peek());while (!heap.isEmpty()) {System.out.println(heap.poll());}}
五、堆的时间复杂度
堆结构的时间复杂度主要是看 heapInsert 和 heapify 两个方法。
它们的操作始终与树的高度紧密相关每次只有一个节点调换整体是复杂度都是 O(logN)。
