南京医院网站建设方案,深圳注明企业网站设计,登录页面设计图片,国家市场监督管理题目描述 实现思路
要实现一个堆#xff0c;我们首先要了解堆的概念。
堆是一种完全二叉树#xff0c;分为大顶堆和小顶堆。 大顶堆#xff1a;每个节点的值都大于或等于其子节点的值。 小顶堆#xff1a;每个节点的值都小于或等于其子节点的值。
完全二叉树#xff…题目描述 实现思路
要实现一个堆我们首先要了解堆的概念。
堆是一种完全二叉树分为大顶堆和小顶堆。 大顶堆每个节点的值都大于或等于其子节点的值。 小顶堆每个节点的值都小于或等于其子节点的值。
完全二叉树在一颗二叉树中若除最后一层外的其余层都是满的并且最后一层要么是满的要么在右边缺少连续若干节点。 回到原题实现一个大顶堆使用数组作为底层数据结构并提供以下操作 添加元素add向堆中添加一个元素。 删除堆顶元素poll删除并返回堆顶元素即最大值。 首先我们需要明白一个事
jdk提供的堆结构也就是PriorityQueue优先级队列删除堆顶元素remove(),poll()会进行下
沉操作向最后插入元素(add(),offer())会进行上浮操作因为有这两个操作所以在堆中删除
堆顶元素向最后插入元素不会改变堆结构。
但是向堆的中间进行插入或修改就会改变堆结构不会自己调整
所以我们实现堆也得需要实现上浮和下沉操作
并且在上浮和下沉过程中还需要交换元素所以我们还需要实现一个数组中元素交换的函数 代码实现 class MaxHeap{//存储堆中元素的数组int[] heap;//堆中元素的个数int size;//堆的初始容量超出容量add函数里2倍扩容int capacity;public MaxHeap(int capacity) {this.capacity capacity;heap new int[capacity];size 0;}public void add(int value) {//判断是否需要扩容if(size capacity) {capacity capacity * 2;int[] newHeap new int[capacity];System.arraycopy(heap,0,newHeap,0,size);heap newHeap;}heap[size] value;size;heapifyUp();}//上浮操作维持堆的性质public void heapifyUp() {//当前节点对应在数组中的索引int index size - 1;//父节点的在数组中的索引 -- 只能有一个父节点int parentIndex (index - 1) / 2;while(parentIndex 0 heap[parentIndex] heap[index]) {swap(heap,parentIndex,index);index parentIndex;parentIndex (index - 1) / 2;}}//删除并返回堆顶元素public int poll() {//判断堆中是否有元素if(size 0) {return Integer.MIN_VALUE;}int maxValue heap[0];heap[0] heap[size - 1];size--;heapifyDown();return maxValue;}//下沉操作维持堆的性质public void heapifyDown() {int index 0;//一个节点有两个子节点int leftChildIndex 2 * index 1;int rightChildIndex 2 * index 2;while(leftChildIndex size) {//找到左右子节点中比较大的那个int largerChildIndex leftChildIndex;if(rightChildIndex size heap[rightChildIndex] heap[leftChildIndex]) {largerChildIndex rightChildIndex;}//如果当前节点大于等于最大的子节点堆性质已经满足if(heap[index] heap[largerChildIndex]) {break;}swap(heap,index,largerChildIndex);index largerChildIndex;leftChildIndex 2 * index 1;rightChildIndex 2 * index 2;}}public void swap(int[] nums,int i,int j) {int temp nums[i];nums[i] nums[j];nums[j] temp;}} 类似题目
【模板】堆_牛客题霸_牛客网215. 数组中的第K个最大元素 - 力扣LeetCode
