Java数据结构之堆(优先队列)的实现
堆（优先队列）是一种典型的数据结构，其形状是一棵完全二叉树，一般用于求解topk问题。根据双亲节点大于等于孩子节点或双亲节点小于等于孩子节点，可分为大顶堆和小顶堆，本文实现大顶堆。
根据大顶堆的定义，大顶堆的双亲节点大于等于其孩子节点，堆顶元素最大，对于每一个子树都是一个大顶堆，则从最后一个双亲节点进行调整为大顶堆，一直到根节点，则可构建一个大顶堆。
我们这里采用数组去存储，以heap={3,2,1,5,6,4}为例，需要一个init(int[] heap)初始化方法，从最后一个双亲节点开始将heap逐渐调整为大顶堆，其中需要使用到adjust(int[] heap, int i, int end)方法。
调整过程：从最后一个双亲节点出发，如果以当前双亲节点为根的树不符合大顶堆，则进行调整。
代码实现如下：
public void init(int[] heap) {
//从最后一个双亲节点开始调整
//逐渐往上进行调整
for (int i = heap.length / 2 ; i > 0 ; i-- ) {
this.adjust(heap, i, heap.length);
}
}
public void adjust(int[] heap, int i, int end) {
int j = i << 1;
while (j <= end) {
//找到两个孩子节点z中较大的节点
if (j < end && heap[j - 1] < heap[j]) {
j = j + 1;
}
//如果较大节点还小于根节点，则以当前节点为根节点的
//二叉树已经是大顶堆，不需要进行调整
if (heap[i - 1] > heap[j - 1]) {
break;
}
//进行调整，将当前节点换到较大位置，再从当前位置进行调整
int temp = heap[i - 1];
heap[i - 1] = heap[j - 1];
heap[j - 1] = temp;
i = j;
j = i << 1;
}
}
构建好了大顶堆之后，我们如何求得topk呢，此时堆顶元素为top1，我们只需要将top1元素拿走，将剩下元素调整为大顶堆，k次之后即可得到topk。
具体过程：我们将堆顶元素与最后一个元素进行交换，然后将堆顶到倒数第二个元素进行调整，依次类推。
以leetcode215数组中第k个最大元素为例：
给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素
public int findKthLargest(int[] nums, int k) {
this.init(nums);
//找到第k大的数
int end = nums.length;
while (k > 1) {
//将当前堆顶元素放到末尾，进行堆调整
int temp = nums[0];
nums[0] = nums[end - 1];
nums[end - 1] = temp;
end = end - 1;
-- k;
this.adjust(nums, 1, end);
}
return nums[0];
}
此外，Java本身提供了优先队列集合类，但是对于这个题目效率不如自己实现的高
public int findKthLargest(int[] nums, int k) {
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(k);
for (int num : nums) {
if (priorityQueue.size() == k) {
if (num > priorityQueue.peek()) {
priorityQueue.poll();
priorityQueue.add(num);
}
continue;
}
priorityQueue.add(num);
}
return priorityQueue.poll();
}
到此这篇关于Java数据结构之堆(优先队列)的实现的文章就介绍到这了,更多相关Java 堆内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！
相关推荐
-
Java基于堆结构实现优先队列功能示例
本文实例讲述了Java基于堆结构实现优先队列功能.分享给大家供大家参考,具体如下: package Demo; import java.util.NoSuchElementException; /* * 小顶堆 java使用堆结构实现优先队列 */ public class JPriorityQueue<E> { @SuppressWarnings("hiding") class QueueNode<E> { int capacity; int size; E[
-
Java堆&优先级队列示例讲解(下)
目录 1.优先级队列 1.1 概念 1.2 内部原理 1.3 操作-入队列 1.4 操作-出队列(优先级最高) 1.5 借用堆实现优先级队列 1.6 测试 1.优先级队列 1.1 概念 在很多应用中,我们通常需要按照优先级情况对待处理对象进行处理,比如首先处理优先级最高的对象,然后处理次高的对象.最简单的一个例子就是,在手机上玩游戏的时候,如果有来电,那么系统应该优先处理打进来的电话.在这种情况下,我们的数据结构应该提供两个最基本的操作,一个是返回最高优先级对象,一个是添加新的对象.这种数据结构
-
Java深入了解数据结构之优先级队列(堆)
目录 一,二叉树的顺序存储 ①存储方式 ②下标关系 ③二叉树顺序遍历 二,堆 ①概念 ②操作-向下调整 ③建堆(建大堆为例) 三,堆的应用-优先级队列 ①概念 ②内部原理 ③入队列 ④出队列(优先级最高) ⑤返回队首元素(优先级最高) 四,堆排序 一,二叉树的顺序存储 ①存储方式 使用数组保存二叉树结构,方式即将二叉树用层序遍历方式放入数组中. 一般只适合表示完全二叉树,因为非完全二叉树会有空间的浪费. 这种方式的主要用法就是堆的表示. ②下标关系 已知双亲(parent)的下标,则: 左孩子(
-
java数据结构-堆实现优先队列
目录 一.二叉树的顺序存储 1.堆的存储方式 2.下标关系 二.堆(heap) 1.概念 2.大/小 根堆 2.1小根堆 2.2大根堆 3.建堆操作 3.1向下调整 4.入队操作 4.1向上调整 4.2push 入队的完整代码展示 5.出队操作 5.1pop 出队代码完全展示 6.查看堆顶元素 7.TOK 问题 7.1TOPK 8.堆排序 文章内容介绍大纲 一.二叉树的顺序存储 1.堆的存储方式 使用数组保存二叉树结构,方式即将二叉树用层序遍历方式放入数组中. 一般只适合表示完全二叉树,因为非完
-
Java堆&优先级队列示例讲解(上)
目录 1. 二叉树的顺序存储 1.1 存储方式 1.2 下标关系 2. 堆(heap) 2.1 概念 2.2 操作-(下沉&上浮)本例是最大堆 2.3 建堆-完整代码(最大堆) 3. 优先级队列 1. 二叉树的顺序存储 1.1 存储方式 使用数组保存二叉树结构,方式即将二叉树用 层序遍历 方式放入数组中. 一般只适合表示完全二叉树,这种方式的主要用法就是堆的表示. 因为非完全二叉树会有空间的浪费(所有非完全二叉树用链式存储). 1.2 下标关系 已知双亲 (parent) 的下标,则: 左孩子
-
Java数据结构之优先级队列(堆)图文详解
目录 一.堆的概念 二.向下调整 1.建初堆 2.建堆 三.优先级队列 1.什么是优先队列? 2.入队列 3.出队列 4.返回队首元素 5.堆的其他TopK问题 总结: 总结 一.堆的概念 堆的定义:n个元素的序列{k1 , k2 , … , kn}称之为堆,当且仅当满足以下条件时: (1)ki >= k2i 且 ki >= k(2i+1) ——大根堆 (2) ki <= k2i 且 ki <= k(2i+1) ——小根堆 简单来说: 堆是具有以下性质的完全二叉树:(1)每个结点的
-
Java数据结构之堆(优先队列)的实现
堆(优先队列)是一种典型的数据结构,其形状是一棵完全二叉树,一般用于求解topk问题.根据双亲节点大于等于孩子节点或双亲节点小于等于孩子节点,可分为大顶堆和小顶堆,本文实现大顶堆. 根据大顶堆的定义,大顶堆的双亲节点大于等于其孩子节点,堆顶元素最大,对于每一个子树都是一个大顶堆,则从最后一个双亲节点进行调整为大顶堆,一直到根节点,则可构建一个大顶堆. 我们这里采用数组去存储,以heap={3,2,1,5,6,4}为例,需要一个init(int[] heap)初始化方法,从最后一个双亲节点开始将h
-
Java数据结构之堆(优先队列)详解
目录 堆的性质 堆的分类 堆的向下调整 堆的建立 堆得向上调整 堆的常用操作 入队列 出队列 获取队首元素 TopK 问题 例子 数组排序 堆的性质 堆逻辑上是一棵完全二叉树,堆物理上是保存在数组中 . 总结:一颗完全二叉树以层序遍历方式放入数组中存储,这种方式的主要用法就是堆的表示. 并且 如果已知父亲(parent) 的下标, 则: 左孩子(left) 下标 = 2 * parent + 1; 右孩子(right) 下标 = 2 * parent + 2; 已知孩子(不区分左右)(child
-
Java 数据结构之堆的概念与应用
目录 什么是堆 堆的类型 小根堆 大根堆 堆的基本操作:创建堆 堆的时间复杂度和空间复杂度 堆的应用-优先级队列 概念 优先级队列基本操作 入优先级队列 出优先级队列首元素 java的优先级队列 堆的常见面试题 最后一块石头的重量 找到K个最接近的元素 查找和最小的K对数字 java数据结构的堆 什么是堆 堆指的是使用数组保存完全二叉树结构,以层次遍历的方式放入数组中. 如图: 注意:堆方式适合于完全二叉树,对于非完全二叉树若使用堆则会造成空间的浪费 对于根节点与其左右孩子在数组中的下标关系可表
-
Java 数据结构与算法系列精讲之二叉堆
目录 概述 优先队列 二叉堆 二叉堆实现 获取索引 添加元素 siftUp 完整代码 概述 从今天开始, 小白我将带大家开启 Java 数据结构 & 算法的新篇章. 优先队列 优先队列 (Priority Queue) 和队列一样, 是一种先进先出的数据结构. 优先队列中的每个元素有各自的优先级, 优先级最高的元素最先得到服务. 如图: 二叉堆 二叉堆 (Binary Heap) 是一种特殊的堆, 二叉堆具有堆的性质和二叉树的性质. 二叉堆中的任意一节点的值总是大于等于其孩子节点值. 如图: 二
-
Java数据结构优先队列实练
目录 最后一块石头的重量 题目描述 思路详解 代码与结果 装满杯子需要的最短总时长 题目描述 思路详解 代码与结果 移除石子的最大得分 题目描述 思路详解 代码与结果 最后一块石头的重量 题目描述 思路详解 这里采用最大堆进行解题. 我们首先考虑,每次拿出两个最大的进行比较,然后大的减去小的重新放入不就完成了嘛. 首先我们创建一个优先队列,遍历重量,放入队列.依次取出重量最大的和第二大的,如果a>b就把a-b重新放入.直到队列里面的元素只剩1个的时候,输出结果. 代码与结果 class Solu
-
Java数据结构之最小堆和最大堆的原理及实现详解
目录 一.前言 二.堆的数据结构 三.堆的代码实现 1. 实现介绍 2. 入堆实现 3. 出堆实现 4. 小堆实现 5. 大堆实现 一.前言 堆的历史 堆的数据结构有很多种体现形式,包括:2-3堆.B堆.斐波那契堆,而在 Java API 中最常用的是用于实现优先队列的二叉堆,它是由 JWJ Williams 在 1964 年引入的,作为堆排序算法的数据结构.另外在 Dijkstra 算法等几种高效的图算法中,堆也是非常重要的. 二.堆的数据结构 在计算机科学中,堆(heap) 的实现是一种基于
-
Java数据结构之栈与队列实例详解
目录 一,栈 1,概念 2,栈的操作 3,栈的实现 4,实现mystack 二,队列 1,概念 2,队列的实现 3,实现myqueue 栈.队列与数组的区别? 总结 一,栈 1,概念 在我们软件应用 ,栈这种后进先出数据结构的应用是非常普遍的.比如你用浏 览器上网时不管什么浏览器都有 个"后退"键,你点击后可以接访问顺序的逆序加载浏览过的网页. 很多类似的软件,比如 Word Photoshop 等文档或图像编 软件中 都有撤销 )的操作,也是用栈这种方式来实现的,当然不同的
-
常用的Java数据结构知识点汇总
目录 1.数据结构分类 2.线性数据结构 2.1数组 2.2可变数组 2.3链表 2.4栈 2.5队列 3.非线性数据结构 3.1树 3.2图 3.3散列表 3.4堆 1. 数据结构分类 按照线性和非线性可以将Java数据结构分为两大类: ①线性数据结构:数组.链表.栈.队列②非线性数据结构:树.堆.散列表.图 2. 线性数据结构 2.1 数组 数组是一种将元素存储于连续内存空间的数据结构,并且要求元素的类型相同. // 定义一个数组长度为5的数组array int[] array = new