二叉堆详解实现优先级队列 :: labuladong的算法小抄 #1039
Replies: 29 comments 7 replies
-
|
这篇对应哪些题？ |
Beta Was this translation helpful? Give feedback.
-
|
最后有提到，可以点击那个链接。 |
Beta Was this translation helpful? Give feedback.
-
|
上一题的求中位数，你就可以用这个二叉堆而不是 JKD 的优先级队列实现一把 |
Beta Was this translation helpful? Give feedback.
-
|
首先，二叉堆和二叉树有啥关系呢，为什么人们总 数 把二叉堆画成一棵二叉树？这里面把是打错成了数吧。 |
Beta Was this translation helpful? Give feedback.
-
|
@Retr0ve 打错了，我改下，感谢指出 |
Beta Was this translation helpful? Give feedback.
-
|
请问left(k)代表什么意思啊？是索引还是value |
Beta Was this translation helpful? Give feedback.
-
返回索引为k的左儿子的索引，也就是2 * k |
Beta Was this translation helpful? Give feedback.
-
|
感谢作者的讲解 :D |
Beta Was this translation helpful? Give feedback.
-
|
笔记: 两个重要操作: 上浮swim(k) 下沉sink(k) |
Beta Was this translation helpful? Give feedback.
-
|
关于为什么0这个下标不用，我有2疑问， |
Beta Was this translation helpful? Give feedback.
-
|
@codefans 是的，也可以通过简单的运行计算下标，只是稍微有些麻烦，你非要在 0 里面放数据，当然也是没问题的。 |
Beta Was this translation helpful? Give feedback.
-
class Heap {
constructor() {
this.heapArr = [];
}
getLeftIndex(parentIndex) {
return parentIndex * 2 + 1
}
getRightIndex(parentIndex) {
return parentIndex * 2 + 2
}
getParentIndex(childIndex) {
return Math.floor((childIndex - 1) / 2)
}
hasLeft(parentIndex) {
return this.getLeftIndex(parentIndex) < this.heapArr.length
}
hasRight(parentIndex) {
return this.getRightIndex(parentIndex) < this.heapArr.length
}
hasParent(childIndex) {
return this.getParentIndex(childIndex) >= 0
}
getLeft(parentIndex) {
return this.heapArr[parentIndex * 2 + 1]
}
getRight(parentIndex) {
return this.heapArr[parentIndex * 2 + 2]
}
getParent(childIndex) {
return this.heapArr[Math.floor((childIndex - 1) / 2)]
}
swap(index1, index2) {
let temp = this.heapArr[index1]
this.heapArr[index1] = this.heapArr[index2]
this.heapArr[index2] = temp
}
/**
* 获取堆顶第一个元素
*/
peek() {
if (this.heapArr.length == 0) {
return null
}
return this.heapArr[0]
}
/**
* 弹出堆顶元素，堆大小发生变化
*/
delMax() {
if (this.heapArr.length == 0) {
return null
}
if (this.heapArr.length == 1) {
return this.heapContainer[0]
}
let item = this.heapArr[0]
// 将最后一个移动到最前面
this.heapArr[0] = this.heapArr.pop()
this.heapifyDown()
return item
}
/**
* 往堆添加一个元素
*/
insert(item) {
this.heapArr.push(item)
// 上浮
this.heapifyUp()
}
/**
* 上浮
*/
heapifyUp(customStartIndex) {
let currentIndex = customStartIndex || this.heapArr.length - 1
// 如果 父小于当前节点进行交换
while (this.hasParent(currentIndex) && this.heapArr[currentIndex] >= this.getParent(currentIndex)) {
this.swap(currentIndex, this.getParentIndex(currentIndex))
currentIndex = this.getParentIndex(currentIndex)
}
}
/**
* 下沉
*/
heapifyDown(customStartIndex = 0) {
let currentIndex = customStartIndex
let nextIndex = null
while(this.hasLeft(currentIndex)) {
if (this.hasRight(currentIndex) && this.getLeft(currentIndex) <= this.getRight(currentIndex)) {
nextIndex = this.getRightIndex(currentIndex)
} else {
nextIndex = this.getLeftIndex(currentIndex)
}
if (this.heapArr[currentIndex] >= this.heapArr[nextIndex]) {
break;
}
console.log(currentIndex, nextIndex, this.heapArr, '=======>')
this.swap(currentIndex, nextIndex)
currentIndex = nextIndex
}
}
} |
Beta Was this translation helpful? Give feedback.
-
|
下沉操作的 |
Beta Was this translation helpful? Give feedback.
-
// TS大根堆的实现（优先队列）
class MaxPQ {
private pq:Array<number> = new Array()
private size:number = 0
public max():number {
return this.pq[1]
}
private swap(i:number, j:number):void {
let temp = this.pq[i]
this.pq[i] = this.pq[j]
this.pq[j] = temp
}
private less(i:number, j:number):boolean {
return this.pq[i] < this.pq[j]
}
private left(x:number):number {
return 2 * x
}
private right(x:number):number {
return 2 * x + 1
}
private parent(x:number):number {
return ~~(x/2)
}
private swim(x:number):void {
while (x > 1 && this.less(this.parent(x), x)) {
this.swap(this.parent(x), x)
x = this.parent(x)
}
}
private sink(x:number):void {
while(this.left(x) <= this.size) {
let max = this.left(x)
if (this.right(x) <= this.size && this.less(max, this.right(x))) {
max = this.right(x)
}
if (this.less(max, x)) break
this.swap(x, max)
x = max
}
}
public insert(e:number):void {
this.size += 1
this.pq[this.size] = e
this.swim(this.size)
}
public delMax():number {
let max:number = this.pq[1]
this.swap(1, this.size)
this.pq[this.size] = null
this.size -= 1
this.sink(1)
return max
}
} |
Beta Was this translation helpful? Give feedback.
-
|
不知道是不是我想多了还是……插入函数是不是要判断size是否越界？越界了则判断待插入元素是否比最后一个元素小，如果是就不用插入了，如果不是则覆盖最后一个元素并上浮 |
Beta Was this translation helpful? Give feedback.
-
可设置比较函数最终版：class PQ<T> {
// 存储元素的数组
private pq:Array<T> = new Array()
// 当前 Priority Queue 中的元素个数
private size:number = 0
// 比较大小的函数，需要在实例化时传入
private cmpFn:Function = null
constructor(fn:Function) {
// 实例化优先级队列时传入比较函数
this.cmpFn = fn
}
/* 返回堆中最大或最小的元素(根据传入的函数判断) */
public top():T {
// 注意索引 0 不用，故索引 1 即为堆顶
return this.pq[1]
}
/* 判断当前堆是否为空 */
public isEmpty():boolean {
return !this.size
}
/* 交换数组的两个元素 */
private swap(i:number, j:number):void {
let temp = this.pq[i]
this.pq[i] = this.pq[j]
this.pq[j] = temp
}
/* 比较两个数据的大小，调用传入的比较函数，当j小的时候上浮(小顶堆) */
private cmp(i:T, j:T):boolean {
return this.cmpFn.call(this, i, j)
}
// 左孩子的索引
private left(x:number):number {
return 2 * x
}
// 右孩子的索引
private right(x:number):number {
return 2 * x + 1
}
// 父节点的索引
private parent(x:number):number {
return ~~(x/2)
}
/* 上浮第 x 个元素，以维护堆性质 */
private swim(x:number):void {
// 如果浮到堆顶，就不能再上浮了，当x小的时候上浮(小顶堆)
while (x > 1 && this.cmp(this.pq[this.parent(x)], this.pq[x])) {
// 将 x 换上去
this.swap(this.parent(x), x)
x = this.parent(x)
}
}
/* 下沉第 x 个元素，以维护堆性质 */
private sink(x:number):void {
// 如果沉到堆底，就沉不下去了
while(this.left(x) <= this.size) {
// 先假设左边节点更大或小
let cur = this.left(x)
// 如果右边节点存在，比一下大小
if (this.right(x) <= this.size && this.cmp(this.pq[cur], this.pq[this.right(x)])) {
cur = this.right(x)
}
// 结点 x 比俩孩子都大或小，就不必下沉了
if (this.cmp(this.pq[cur], this.pq[x])) break
// 否则，不符合最大/小堆的结构，下沉 x 结点
this.swap(x, cur)
x = cur
}
}
/* 加入数据 */
public offer(e:T):void {
this.size += 1
// 先把新元素加到最后
this.pq[this.size] = e
// 然后让它上浮到正确的位置
this.swim(this.size)
}
public poll():T {
// 最大/小堆的堆顶就是最大/小元素
let cur:T = this.pq[1]
// 把这个元素换到最后，删除之
this.swap(1, this.size)
this.pq.pop()
this.size -= 1
// 让 pq[1] 下沉到正确位置
this.sink(1)
return cur
}
} |
Beta Was this translation helpful? Give feedback.
-
|
啊 知道了怎么从数组到二叉堆到优先队列，比只是知道怎么用优先队列有意思多了，似乎有一种。。。掌控感哈哈哈哈哈 |
Beta Was this translation helpful? Give feedback.
-
|
用优先级队列解决排序数组题 # @param {Integer[]} nums
# @return {Integer[]}
class MinPQ
attr_accessor :pq, :size
def initialize
@pq = []
@pq.push nil
@size = 0
end
def parent root
root / 2
end
def left root
root * 2
end
def right root
root * 2 + 1
end
def min
@pq[1]
end
def insert e
@size += 1
@pq.push e
swim @size
end
def del_min
min = @pq[1]
swap 1, @size
@pq.pop
@size -= 1
sink 1
min
end
def swim x
while x > 1 && more(parent(x), x) do
swap parent(x), x
x = parent x
end
end
def sink x
while left(x) <= size do
min = left x
min = right(x) if right(x) <= size && more(min, right(x))
break if more min, x
swap x, min
x = min
end
end
def swap i, j
@pq[i], @pq[j] = @pq[j], @pq[i]
end
def more i, j
@pq[i] > @pq[j]
end
def empty?
@size == 0
end
end
def sort_array nums
queue = MinPQ.new
nums.each { |num| queue.insert num }
output = []
output.push queue.del_min until queue.empty?
output
end |
Beta Was this translation helpful? Give feedback.
-
|
ruby优先队列解决力扣318周赛第三题 # @param {Integer[]} costs
# @param {Integer} k
# @param {Integer} candidates
# @return {Integer}
class MinPQ
attr_accessor :pq, :size
def initialize
@pq = []
@pq.push nil
@size = 0
end
def parent root
root / 2
end
def left root
root * 2
end
def right root
root * 2 + 1
end
def min
@pq[1]
end
def insert e
@size += 1
@pq.push e
swim @size
end
def del_min
min = @pq[1]
swap 1, @size
@pq.pop
@size -= 1
sink 1
min
end
def swim x
while x > 1 && more(parent(x), x) do
swap parent(x), x
x = parent x
end
end
def sink x
while left(x) <= size do
min = left x
min = right(x) if right(x) <= size && more(min, right(x))
break if more min, x
swap x, min
x = min
end
end
def swap i, j
@pq[i], @pq[j] = @pq[j], @pq[i]
end
def more i, j
@pq[i] > @pq[j]
end
def empty?
@size == 0
end
end
def total_cost(costs, k, candidates)
len = costs.length
if 2 * candidates >= len
costs_sort = costs.sort
return costs_sort[0...k].sum
end
ans = 0
queue1 = MinPQ.new
queue2 = MinPQ.new
lo, hi = candidates, len - candidates
# 区间为[0, lo)和[hi, len)
candidates.times { |i| queue1.insert costs[i] }
(hi...len).each { |i| queue2.insert costs[i] }
k.times do
if !queue1.empty? || !queue2.empty?
if queue1.empty?
ans += queue2.del_min
if lo < hi
hi -= 1
queue2.insert costs[hi]
end
elsif queue2.empty?
ans += queue1.del_min
if lo < hi
queue1.insert costs[lo]
lo += 1
end
else
if queue1.min <= queue2.min
ans += queue1.del_min
if lo < hi
queue1.insert costs[lo]
lo += 1
end
else
ans += queue2.del_min
if lo < hi
hi -= 1
queue2.insert costs[hi]
end
end
end
end
end
ans
end |
Beta Was this translation helpful? Give feedback.
-
|
太牛了，虽然内容不多，但讲的简单、清晰👍 |
Beta Was this translation helpful? Give feedback.
-
|
实现了一版带泛型的BinaryHeap，考虑了capacity超出或者delMax时堆为空的异常情况，并支持了peek, size等public方法： public class BinaryHeap<E extends Comparable<E>> {
private E[] arr;
private int size;
private int capacity;
public BinaryHeap(int capacity) {
arr = (E[]) new Comparable[capacity + 1]; // leave index 0 unused
this.capacity = capacity;
size = 0;
}
public void insert(E elem) {
if (size >= capacity) {
throw new IllegalArgumentException("heap is full");
}
size++;
arr[size] = elem;
swim(size);
}
public E delMax() {
if (size == 0) {
throw new IllegalArgumentException("heap is empty");
}
E top = arr[1];
swap(1, size);
arr[size] = null;
size--;
sink(1);
return top;
}
public E peek() {
return arr[1];
}
private void sink(int x) {
while (left(x) <= size) {
int max = left(x);
if (right(x) <= size && less(max, right(x))) {
max = right(x);
}
if (less(max, x)) break;
swap(max, x);
x = max;
}
}
public int size() {
return size;
}
private int left(int x) {
return x * 2;
}
private int right(int x) {
return x * 2 + 1;
}
private void swim(int x) {
while (x > 1 && less(parent(x), x)) {
swap(parent(x), x);
x = parent(x);
}
}
private void swap(int a, int b) {
E tmp = arr[a];
arr[a] = arr[b];
arr[b] = tmp;
}
private boolean less(int a, int b) {
return arr[a].compareTo(arr[b]) < 0;
}
private int parent(int x) {
return x / 2;
}
} |
Beta Was this translation helpful? Give feedback.
-
|
支持扩容的二叉堆 java 实现 public class MaxPriorityQueue<E extends Comparable<E>> {
private E[] arr;
private int size = 0;
public MaxPriorityQueue() {
arr = (E[]) new Comparable[10];
}
public void offer(E e) {
// 扩容
if (++size == arr.length) {
expandCapacity();
}
// 在数组末尾添加元素，不断上浮到正确位置
arr[size] = e;
swim(size);
}
private void expandCapacity() {
E[] temp = (E[]) new Comparable[arr.length * 2];
System.arraycopy(arr, 0, temp, 0, arr.length);
arr = temp;
}
public E poll() {
// 将最大元素和末尾元素进行交换
// 将末尾元素不断下沉到正确位置
E max = arr[1];
swap(size, 1);
arr[size--] = null;
sink(1);
return max;
}
public E peek() {
return arr[1];
}
/**
* 上浮
* @param n
*/
private void swim(int n) {
while (n > 1) {
// 父节点值比 n 所在的值小，则将 n 所在的值替换到父节点值
if (less(parent(n), n)) {
swap(parent(n), n);
n = parent(n);
}
}
}
private void sink(int n) {
// 保证子节点存在，再进行下沉
while (left(n) < size) {
int maxIndex = left(n);
// 找到较大的子节点值
if (less(maxIndex, right(n))) {
maxIndex = right(n);
}
// 父节点值不比子节点值小，则不继续下沉
if (less(maxIndex, n)) {
break;
}
// 将父节点值与较大的子节点值进行替换
swap(maxIndex, n);
n = maxIndex;
}
}
private int parent(int n) {
return n / 2;
}
private int left(int n) {
return 2 * n;
}
private int right(int n) {
return 2 * n + 1;
}
private void swap(int i, int j) {
E temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
private boolean less(int i, int j) {
return arr[i].compareTo(arr[j]) < 0;
}
} |
Beta Was this translation helpful? Give feedback.
-
|
上面的代码有问题，swim 方法应该是 while (n > 1 && less(parent(n), n)) {
// 父节点值比 n 所在的值小，则将 n 所在的值替换到父节点值
swap(parent(n), n);
n = parent(n);
}而不是 while (n > 1) {
// 父节点值比 n 所在的值小，则将 n 所在的值替换到父节点值
if (less(parent(n), n)) {
swap(parent(n), n);
n = parent(n);
}
} |
Beta Was this translation helpful? Give feedback.
-
|
最小二叉堆和最大二叉堆的实现，只要修改一下 less 方法即可。具体代码如下： public class MyPriorityQueue<E extends Comparable<E>> {
private E[] arr;
private int size = 0;
private Comparator<E> comparator;
public MyPriorityQueue() {
this(Comparator.naturalOrder());
}
public MyPriorityQueue(Comparator<E> comparator) {
arr = (E[]) new Comparable[10];
this.comparator = Objects.requireNonNull(comparator);
}
public void offer(E e) {
// 扩容
if (++size == arr.length) {
expandCapacity();
}
// 在数组末尾添加元素，不断上浮到正确位置
arr[size] = e;
swim(size);
}
private void expandCapacity() {
E[] temp = (E[]) new Comparable[arr.length * 2];
System.arraycopy(arr, 0, temp, 0, arr.length);
arr = temp;
}
public E poll() {
// 将最大元素和末尾元素进行交换
// 将末尾元素不断下沉到正确位置
E max = arr[1];
swap(size, 1);
arr[size--] = null;
sink(1);
return max;
}
public E peek() {
return arr[1];
}
/**
* 上浮
* @param n
*/
private void swim(int n) {
// 确保有上浮必要再进行上浮
while (n > 1 && notPrioritize(parent(n), n)) {
// 父节点值比 n 所在的值优先级低，则将 n 所在的值替换到父节点值
swap(parent(n), n);
n = parent(n);
}
}
private void sink(int n) {
// 保证子节点存在，再进行下沉
while (left(n) < size) {
int maxIndex = left(n);
// 找到优先级高的子节点值
if (notPrioritize(maxIndex, right(n))) {
maxIndex = right(n);
}
// 父节点值优先级比子节点值高，则不继续下沉
if (notPrioritize(maxIndex, n)) {
break;
}
// 将父节点值优先级高的子节点值进行替换
swap(maxIndex, n);
n = maxIndex;
}
}
private int parent(int n) {
return n / 2;
}
private int left(int n) {
return 2 * n;
}
private int right(int n) {
return 2 * n + 1;
}
private void swap(int i, int j) {
E temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
private boolean notPrioritize(int i, int j) {
return comparator.compare(arr[i], arr[j]) > 0;
}
// usage
public static void main(String[] args) {
MyPriorityQueue<Integer> minQueue = new MyPriorityQueue<>();
MyPriorityQueue<Integer> maxQueue = new MyPriorityQueue<>((i1, i2) -> i2 - i1);
}
} |
Beta Was this translation helpful? Give feedback.
-
|
提个建议：gif动画看的太费劲，没办法自行调整进度，看的太麻烦，希望改进。文章内容非常好，谢谢作者 |
Beta Was this translation helpful? Give feedback.
-
|
已收到
|
Beta Was this translation helpful? Give feedback.
-
|
这是我根据阿东的二叉堆，顺便写了个小顶堆。有了大顶堆和小顶堆，就可以实现上一篇文章中的《求数组的中位数》，数组中位数的解法的时间和空间复杂度最小的方式就是使用两个堆，一个大顶堆一个小顶堆 public class MedianFinder {
private static final int PQ_SIZE = 2 * 100_000;
private MinPq<Integer> largePq = new MinPq<>(PQ_SIZE);
private MaxPq<Integer> smallPq = new MaxPq<>(PQ_SIZE);
public void addNumC2(int num) {
if (smallPq.size() >= largePq.size()) {
// 向 laregePq 新增元素
smallPq.insert(num);
largePq.insert(smallPq.delMax());
} else {
largePq.insert(num);
smallPq.insert(largePq.delMin());
}
}
public double findMedianC2() {
if (smallPq.size() > largePq.size()) {
return smallPq.max();
} else if (smallPq.size() < largePq.size()) {
return largePq.min();
}
// 二者 size 相等
return (smallPq.max() + largePq.min()) / 2.0;
}
}
public class MinPq<K extends Comparable<K>> {
private K[] pq;
private int size;
public MinPq(int n) {
this.pq = (K[]) new Comparable[n + 1];
}
// 仍然是辅助方法
private int parent(int k) {
return k / 2;
}
private int left(int k) {
return k * 2;
}
private int right(int k) {
return k * 2 + 1;
}
private void swap(int i, int j) {
K tmp = pq[i];
pq[i] = pq[j];
pq[j] = tmp;
}
private boolean less(int i, int j) {
return pq[i] != null && pq[i].compareTo(pq[j]) < 0;
}
// 核心方法
private void sink(int k) {
while (left(k) <= size) {
int child = left(k);
if (right(k) <= size && less(right(k), child)) {
child = right(k);
}
// k 比最小的左右子节点还小，满足条件，退出循环
if (less(k, child)) {
break;
}
swap(k, child);
k = child;
}
}
private void swim(int k) {
while (k > 1 && less(k, parent(k))) {
swap(k, parent(k));
k = parent(k);
}
}
public K min() {
return pq[1];
}
public void insert(K k) {
size++;
pq[size] = k;
swim(size);
}
public K delMin() {
K k = pq[1];
swap(1, size);
pq[size] = null;
size--;
sink(1);
return k;
}
public int size() {
return size;
}
}
public class MaxPq<K extends Comparable<K>> {
//.... 参照 阿东的写法
} |
Beta Was this translation helpful? Give feedback.
-
|
C++参考， 没有测试太多， 但是应该没什么问题 #include <ios>
#include<vector>
using namespace std;
template <class T>
class MaxPQ
{
public:
MaxPQ(size_t size): container(size)
{
}
MaxPQ(): container(0)
{
}
~MaxPQ()
{
container.clear();
}
void insert(T newEle)
{
container.push_back(newEle);
swim(container.size() - 1);
}
/* 删除并返回当前队列中最大元素 */
T delMax()
{
T result = max();
swapByIndex(0, container.size() - 1);
container.erase(container.end());
sink(0);
return result;
}
inline T max()
{
return container[0];
}
void swapByIndex(size_t Left, size_t Right)
{
using std::swap;
swap(container[left], container[right]);
}
inline bool isLess(size_t Left, size_t Right)
{
return container[Left] < container[Right];
}
inline size_t left(size_t parent)
{
return parent * 2 + 1;
}
inline size_t right(size_t parent)
{
return parent * 2 + 2;
}
inline size_t parent(size_t child)
{
return (child - 1) >= 0 ? (child - 1) / 2 : -1;
}
private:
vector<T> container;
void swim(size_t targetIndex)
{
while (targetIndex > 0 && isLess(parent(targetIndex), targetIndex))
{
swapByIndex(parent(targetIndex), targetIndex);
targetIndex = parent(targetIndex);
}
}
void sink(size_t targetIndex)
{
while (left(targetIndex) < container.size())
{
size_t maxIndex = left(targetIndex);
if (right(targetIndex) < container.size() && isLess(maxIndex, right(targetIndex)))
{
maxIndex = right(targetIndex);
}
if (isLess(maxIndex, targetIndex))
{
break;
}
swapByIndex(targetIndex, maxIndex);
targetIndex = maxIndex;
}
}
};
|
Beta Was this translation helpful? Give feedback.
-
|
详细测试了一下 问题比较多 大家看个乐呵就行 |
Beta Was this translation helpful? Give feedback.
-
|
改完的版本就懒得放出来了 |
Beta Was this translation helpful? Give feedback.
-
|
稍微改了一下 #include <iostream>
#include<vector>
template <class T>
class MaxPQ
{
public:
MaxPQ(size_t size): container(size)
{
}
MaxPQ(std::vector<T>& Raw)
{
container.clear();
for (const auto& val : Raw)
{
this->insert(val);
}
}
MaxPQ(): container(0)
{
}
~MaxPQ()
{
container.clear();
}
void insert(T newEle)
{
container.push_back(newEle);
swim(container.size() - 1);
}
/* 删除并返回当前队列中最大元素 */
T delMax()
{
T result = max();
swapByIndex(0, container.size() - 1);
container.erase(container.end());
sink(0);
return result;
}
inline T max()
{
return container[0];
}
void swapByIndex(size_t Left, size_t Right)
{
using std::swap;
swap(container[Left], container[Right]);
}
inline bool isLess(size_t Left, size_t Right)
{
return container[Left] < container[Right];
}
inline size_t left(size_t parent)
{
return parent * 2 + 1;
}
inline size_t right(size_t parent)
{
return parent * 2 + 2;
}
inline size_t parent(size_t child)
{
return (child - 1) >= 0 ? (child - 1) / 2 : -1;
}
void print()
{
using std::cout;
for (const auto& val : container)
cout << val << " ";
cout << std::endl;
}
private:
std::vector<T> container;
void swim(size_t targetIndex)
{
while (targetIndex > 0 && isLess(parent(targetIndex), targetIndex))
{
swapByIndex(parent(targetIndex), targetIndex);
targetIndex = parent(targetIndex);
}
}
void sink(size_t targetIndex)
{
while (left(targetIndex) < container.size())
{
size_t maxIndex = left(targetIndex);
if (right(targetIndex) < container.size() && isLess(maxIndex, right(targetIndex)))
{
maxIndex = right(targetIndex);
}
if (isLess(maxIndex, targetIndex))
{
break;
}
swapByIndex(targetIndex, maxIndex);
targetIndex = maxIndex;
}
}
};
int main()
{
std::vector<int> temp{1, 8, 0, 9, 12, 4};
auto myPQ = new MaxPQ<int>(temp);
myPQ->print();
} |
Beta Was this translation helpful? Give feedback.
-
|
已收到
|
Beta Was this translation helpful? Give feedback.
-
|
如果要删除中间元素是怎么操作的？ |
Beta Was this translation helpful? Give feedback.
-
|
已收到
|
Beta Was this translation helpful? Give feedback.
-
|
之前实现过一个 class PriorityQueue1 {
constructor() {
this.heap = [];
}
// 构建优先级队列
enqueue(element, priority) {
const node = { element, priority };
this.heap.push(node); // 最后位置插入
this.bubbleUp();
}
// 获取堆顶元素
dequeue() {
if (this.isEmpty()) {
return null;
}
const minNode = this.heap[0];
const lastNode = this.heap.pop();
if (this.heap.length > 0) {
this.heap[0] = lastNode;
this.bubbleDown();
}
return minNode.element;
}
isEmpty() {
return this.heap.length === 0;
}
swap(i, j) {
const temp = this.heap[i];
this.heap[i] = this.heap[j];
this.heap[j] = temp;
}
// 构建优先级队列时的操作，push元素，与父级元素比较,构建最小堆（只和父节点比较，兄弟节点不用）
bubbleUp() {
let index = this.heap.length - 1;
while (index > 0) {
const element = this.heap[index];
const parentIndex = Math.floor((index - 1) / 2);
const parent = this.heap[parentIndex];
if (element.priority < parent.priority) {
this.swap(index, parentIndex);
index = parentIndex;
} else {
break;
}
}
}
/* 操作用于确保在删除最小优先级元素后，最小堆的性质仍然得以保持。
* 在删除最小元素后，为了保持最小堆性质，需要将堆的根节点替换为最后一个节点，
* 并从根节点开始，将其与其子节点比较，如果有子节点的优先级更小，则交换它们的位置，
* 一直重复这个过程，直到最小堆的性质被恢复。
* 这个过程确保在删除最小元素后，堆仍然是一个最小堆。
*/
bubbleDown() {
let index = 0;
while (true) {
let smallestChildIndex = index;
const leftChildIndex = 2 * index + 1;
const rightChildIndex = 2 * index + 2;
if (leftChildIndex < this.heap.length && this.heap[leftChildIndex].priority < this.heap[smallestChildIndex].priority) {
smallestChildIndex = leftChildIndex;
}
if (rightChildIndex < this.heap.length && this.heap[rightChildIndex].priority < this.heap[smallestChildIndex].priority) {
smallestChildIndex = rightChildIndex;
}
if (smallestChildIndex !== index) {
this.swap(index, smallestChildIndex);
index = smallestChildIndex;
}
else {
break;
}
}
}
} |
Beta Was this translation helpful? Give feedback.
-
|
已收到
|
Beta Was this translation helpful? Give feedback.
and others
Uh oh!
There was an error while loading. Please reload this page.
Uh oh!
There was an error while loading. Please reload this page.
-
文章链接点这里：二叉堆详解实现优先级队列
评论礼仪 见这里，违者直接拉黑。
Beta Was this translation helpful? Give feedback.
All reactions