摘要:我理解的數據結構七堆和優先隊列一堆堆的基礎堆也是一顆樹堆最為主流的一種實現方式二叉堆二叉堆是一顆完全二叉樹完全二叉樹完全二叉樹是效率很高的數據結構,完全二叉樹是由滿二叉樹而引出來的。
我理解的數據結構(七)—— 堆和優先隊列(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;
}
}
文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。
轉載請注明本文地址:http://specialneedsforspecialkids.com/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...
摘要:堆分為大根堆和小根堆,大根堆是父節點大于左右子節點,并且左右子樹也滿足該性質的完全二叉樹。其中表示向下取整。則一直指向,一直指向,因為我們在調整堆結構中實際調整的是索引數組,而不會改變真實存放數據的數組。以上就是實現對和索引堆的具體方式。 堆是一棵完全二叉樹。堆分為大根堆和小根堆,大根堆是父節點大于左右子節點,并且左右子樹也滿足該性質的完全二叉樹。小根堆相反。可以利用堆來實現優先隊列。...
閱讀 2501·2021-09-28 09:36
閱讀 1504·2021-09-22 15:33
閱讀 3641·2019-08-30 15:44
閱讀 1749·2019-08-29 13:14
閱讀 3137·2019-08-29 11:17
閱讀 1451·2019-08-29 11:03
閱讀 2910·2019-08-26 17:10
閱讀 686·2019-08-26 12:13