摘要:我理解的数据结构七堆和优先队列一堆堆的基础堆也是一颗树堆最为主流的一种实现方式二叉堆二叉堆是一颗完全二叉树完全二叉树完全二叉树是效率很高的数据结构,完全二叉树是由满二叉树而引出来的。
我理解的数据结构(七)—— 堆和优先队列(Heap And PriorityQueue) 一、堆
1.堆的基础
堆也是一颗树
堆最为主流的一种实现方式:二叉堆
二叉堆是一颗完全二叉树
2.完全二叉树
完全二叉树是效率很高的数据结构,完全二叉树是由满二叉树而引出来的。对于深度为K的,有n个结点的二叉树,当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。
(通俗来说:完全二叉树不一定是满二叉树,当一层已满容纳不下新的节点时,新的一层从左至右来盛放新节点,缺失的节点一定在右侧)
最大堆:堆中某个节点的值总是不大于其父节点的值(相应的,可以定义最小堆)
3.用数组存储二叉堆
4.基础代码实现
这里的ArrayNew是我之前实现的数组:数组代码
public class Heap> { private ArrayNew data; public Heap(int capacity) { data = new ArrayNew<>(capacity); } public Heap() { data = new ArrayNew<>(); } // 返回堆中的元素个数 public int size() { return data.getSize(); } // 堆中是否包含元素 public boolean isEmpty() { return data.isEmpty(); } // 父节点的索引 private int parent(int index) { if (index == 0) { throw new IllegalArgumentException("index-0 doesn"t have parent"); } return (index - 1) / 2; } // 左子节点的索引 private int leftChild(int index) { return 2 * index + 1; } // 右子节点的索引 private int rightChild(int index) { return 2 * index + 2; } }
5.添加元素(sift up)
步骤:
在最后一层的最后添加这个元素,如果是满树,则在新的一层最左端添加
与其父节点做比较,如果父节点小于当前元素的节点,置换位置
以此类推,直到比较至根节点
// 添加元素 public void add(E e) { data.addLast(e); siftUp(data.getSize() - 1); } // 上浮 private void siftUp(int index) { // 添加的元素大于父节点的元素 while (index > 0 && data.get(index).compareTo(data.get(parent(index))) > 0) { data.swap(index, parent(index)); index = parent(index); } }
6.取出元素(sift down)
步骤:
最后一个节点与根节点交换,取出末尾节点,这样整体树结构不会改变,只是位置不对
根节点与子节点的元素做比较,如果比子节点的最大的节点元素小,则置换位置
以此类推,直至比子节点的元素都大
// 查看堆中的最大值 public E findMax() { if (data.isEmpty()) { throw new IllegalArgumentException("can"t find Max in empty heap"); } return data.get(0); } // 取出堆中的最大值 public E extractMax() { E ret = data.get(0); data.swap(0, data.getSize() - 1); data.removeLast(); siftDown(0); return ret; } // 下沉 private void siftDown(int index) { while (leftChild(index) < data.getSize()) { // 有子节点(左子节点没有越界) int j = leftChild(index); // 有右子节点,并且右节点元素大于左节点元素 if (j + 1 < data.getSize() && data.get(j + 1).compareTo(data.get(j)) > 0) { j = j + 1; } // 此时,data[j]就是左右子节点的最大节点值 if (data.get(j).compareTo(data.get(index)) <= 0) { break; } data.swap(index, j); index = j; } }
7.Heapify和replace
replace(取出堆中的最大元素,再放入一个新的元素)
实现:可以先extractMax再add,但是这样会有两次O(logn)操作
优化:可以将堆顶元素替换以后再siftDown,这样只有一次O(logn)操作
// 取出堆中的最大元素,并替换成元素e,重新siftDown public E replace(E e) { E ret = data.get(0); data.set(0, e); siftDown(0); return ret; }
heapify(将任意数组整理成堆的形状)
实现:将n个元素逐个插入到一个空堆中,算法复杂度是O(logn)
优化:heapify(算法复杂度是O(n))
将任意一个数组看成完全二叉树(尽管元素的位置不对)
找到最后一个非叶子节点(最后一个节点的父节点)
从最后一个非叶子节点倒着不断的对每个节点siftDown就可以了
// heapify public Heap(E[] arr) { data = new ArrayNew<>(arr); for (int i = parent(data.getSize() - 1); i > 0; i--) { siftDown(i); } }
8. 复杂度分析
因为堆的取出和添加复杂度都是O(logn),所以堆的性能是很高的。
操作 | 时间复杂度 |
---|---|
add | O(logn) |
extractMax | O(logn) |
1.优先队列基础
普通队列:先进先出,后进后出
优先队列:出队顺序和入队顺序无关,和优先级有关
2.队列接口
public interface Queue{ int getSize(); boolean isEmpty(); void enqueue(E e); E dequeue(); // 查看队首元素 E getFront(); }
3.基于堆的优先队列代码实现
public class priorityQueue> implements Queue { Heap data; public priorityQueue() { data = new Heap<>(); } @Override public int getSize() { return data.size(); } @Override public boolean isEmpty() { return data.isEmpty(); } @Override public void enqueue(E e) { data.add(e); } @Override public E dequeue() { return data.extractMax(); } @Override public E getFront() { return data.findMax(); } }
4.LeetCode中有关优先队列的问题
347. 前K个高频元素
题目:347. 前K个高频元素
描述:给定一个非空的整数数组,返回其中出现频率前 k 高的元素。
例子:
示例 1: 输入: nums = [1,1,1,2,2,3], k = 2 输出: [1,2] 示例 2: 输入: nums = [1], k = 1 输出: [1]
解决代码:
import java.util.ArrayList; import java.util.List; import java.util.TreeMap; // 只需要在`Solution`这个类中引入所需要的类即可 // 所有的类都可以在之前的博客中找到 public class Solution { private class Freq implements Comparable{ public int e, freq; public Freq(int e, int freq) { this.e = e; this.freq = freq; } @Override public int compareTo(Freq another) { if (this.freq < another.freq) { return 1; } else if (this.freq > another.freq) { return -1; } else { return 0; } } } public List topKFrequent(int[] nums, int k) { TreeMap map = new TreeMap<>(); for (int num : nums) { if (map.containsKey(num)) { map.put(num, map.get(num) + 1); } else { map.put(num, 1); } } PriorityQueue pq = new PriorityQueue<>(); for (int key : map.keySet()) { if (pq.getSize() < k) { pq.enqueue(new Freq(key, map.get(key))); } else if (map.get(key) > pq.getFront().freq) { pq.dequeue(); pq.enqueue(new Freq(key, map.get(key))); } } ArrayList list = new ArrayList<>(); while (!pq.isEmpty()) { list.add(pq.dequeue().e); } return list; } }
文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。
转载请注明本文地址:https://www.ucloud.cn/yun/71800.html
摘要:我理解的数据结构七堆和优先队列一堆堆的基础堆也是一颗树堆最为主流的一种实现方式二叉堆二叉堆是一颗完全二叉树完全二叉树完全二叉树是效率很高的数据结构,完全二叉树是由满二叉树而引出来的。 我理解的数据结构(七)—— 堆和优先队列(Heap And PriorityQueue) 一、堆 1.堆的基础 堆也是一颗树 堆最为主流的一种实现方式:二叉堆 二叉堆是一颗完全二叉树 2.完全二叉树 ...
摘要:一个常见的例子就是优先队列,还有排序算法之一的堆排序。另外我们还将学习堆排序,并将使用实现堆。堆排序在堆排序中,我们需要用给定的值构建一个一个堆。伪代码如下从上面的伪代码可以看到,堆排序的第一步就是构建一个堆。 堆是什么? 堆是基于树抽象数据类型的一种特殊的数据结构,用于许多算法和数据结构中。一个常见的例子就是优先队列,还有排序算法之一的堆排序。这篇文章我们将讨论堆的属性、不同类型的堆...
摘要:项目地址中内置的库和分别提供了堆和优先队列结构,其中优先队列本身也是基于实现的,因此我们这次重点看一下。堆可以用于实现调度器例见之协程,更常用的是优先队列例如。 项目地址:https://git.io/pytips Python 中内置的 heapq 库和 queue 分别提供了堆和优先队列结构,其中优先队列 queue.PriorityQueue 本身也是基于 heapq 实现的,因...
摘要:注意因为堆中是链表节点,我们在初始化堆时还要新建一个的类。代码初始化大小为的堆拿出堆顶元素将堆顶元素的下一个加入堆中 Merge Two Sorted Lists 最新更新请见:https://yanjia.me/zh/2019/01/... Merge two sorted linked lists and return it as a new list. The new list...
摘要:堆分为大根堆和小根堆,大根堆是父节点大于左右子节点,并且左右子树也满足该性质的完全二叉树。其中表示向下取整。则一直指向,一直指向,因为我们在调整堆结构中实际调整的是索引数组,而不会改变真实存放数据的数组。以上就是实现对和索引堆的具体方式。 堆是一棵完全二叉树。堆分为大根堆和小根堆,大根堆是父节点大于左右子节点,并且左右子树也满足该性质的完全二叉树。小根堆相反。可以利用堆来实现优先队列。...
阅读 2492·2021-09-28 09:36
阅读 1486·2021-09-22 15:33
阅读 3636·2019-08-30 15:44
阅读 1743·2019-08-29 13:14
阅读 3132·2019-08-29 11:17
阅读 1441·2019-08-29 11:03
阅读 2905·2019-08-26 17:10
阅读 681·2019-08-26 12:13