二叉堆详解实现优先级队列 :: labuladong的算法小抄 #1039

两个重要操作: 上浮swim(k) 下沉sink(k)
上浮的作用是使得第k个元素不断和父节点比较、上浮, 进而平衡树的优先级. 常常和insert使用, 即将元素插入末位子节点, 然后进行上浮.
下沉的作用是使得第k个元素不断和两个子节点进行比较, 下沉到合适的位置, 平衡优先级. 常常和delMax(删除最大堆的堆顶)使用, 首先将堆首位对调, 删除末位子节点后将首元素下沉到合适位置.

0 replies

codefans · 2022-03-01T23:15:23Z

codefans
Mar 1, 2022

关于为什么0这个下标不用，我有2疑问，
1、只要是按层级遍历二叉堆，然后把遍历结果存入数组，也可以通过：
父节点=(子节点-1)/2
左节点=父节点2+1
右节点=父节点2+2
即使从下标0开始，也可以通过简单的运行计算节点下标；
2、我debug jdk1.8的PriorityQueue源码，发现queue[0]是有数据的，那为什么下标会从1开始呢？

0 replies

labuladong · 2022-03-02T06:34:25Z

labuladong
Mar 2, 2022
Maintainer

@codefans 是的，也可以通过简单的运行计算下标，只是稍微有些麻烦，你非要在 0 里面放数据，当然也是没问题的。

0 replies

hitao123 · 2022-04-05T09:37:45Z

hitao123
Apr 5, 2022

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
        }
    }
}

0 replies

xiaoyuan0203 · 2022-05-17T10:00:00Z

xiaoyuan0203
May 17, 2022

下沉操作的 left(x) <= size 也可以改成 x <= size / 2
上浮操作的 node 似乎是 x ?

0 replies

GeorgeSmith215 · 2022-06-24T08:27:26Z

GeorgeSmith215
Jun 24, 2022

// 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
  }
}

0 replies

ghost · 2022-08-22T08:43:50Z

ghost
Aug 22, 2022

不知道是不是我想多了还是……插入函数是不是要判断size是否越界？越界了则判断待插入元素是否比最后一个元素小，如果是就不用插入了，如果不是则覆盖最后一个元素并上浮

0 replies

GeorgeSmith215 · 2022-08-25T08:12:24Z

GeorgeSmith215
Aug 25, 2022

可设置比较函数最终版：

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
  }
}

0 replies

chloepei867 · 2022-11-11T17:52:34Z

chloepei867
Nov 11, 2022 — with giscus

啊知道了怎么从数组到二叉堆到优先队列，比只是知道怎么用优先队列有意思多了，似乎有一种。。。掌控感哈哈哈哈哈

0 replies

Youareblind · 2022-12-01T13:19:47Z

Youareblind
Dec 1, 2022 — with giscus

用优先级队列解决排序数组题
ruby无优先队列，学习labuladong进行手搓

# @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

0 replies

Youareblind · 2022-12-01T17:57:26Z

Youareblind
Dec 1, 2022 — with giscus

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

0 replies

acmu · 2023-01-01T16:28:16Z

acmu
Jan 1, 2023 — with giscus

太牛了，虽然内容不多，但讲的简单、清晰👍

0 replies

bruceeewong · 2023-03-06T22:10:15Z

bruceeewong
Mar 6, 2023 — with giscus

实现了一版带泛型的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;
    }
}

0 replies

marmot-z · 2023-05-23T14:50:42Z

marmot-z
May 23, 2023 — with giscus

支持扩容的二叉堆 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;
    }
}

2 replies

marmot-z May 24, 2023 — with giscus

上面的代码有问题，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);
            }
        }

marmot-z May 24, 2023 — with giscus

最小二叉堆和最大二叉堆的实现，只要修改一下 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);
    }
}

Zjp-hub · 2023-08-22T14:08:45Z

Zjp-hub
Aug 22, 2023 — with giscus

提个建议：gif动画看的太费劲，没办法自行调整进度，看的太麻烦，希望改进。文章内容非常好，谢谢作者

0 replies

Zjp-hub · 2023-09-12T11:24:37Z

Zjp-hub
Sep 12, 2023

已收到

0 replies

shiboys · 2023-09-17T04:03:23Z

shiboys
Sep 17, 2023 — with giscus

这是我根据阿东的二叉堆，顺便写了个小顶堆。有了大顶堆和小顶堆，就可以实现上一篇文章中的《求数组的中位数》，数组中位数的解法的时间和空间复杂度最小的方式就是使用两个堆，一个大顶堆一个小顶堆

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>> {
   //.... 参照 阿东的写法
}

0 replies

KSroido · 2023-10-12T05:01:50Z

KSroido
Oct 12, 2023 — with giscus

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;
		}
	}
};

3 replies

KSroido Oct 12, 2023 — with giscus

详细测试了一下问题比较多大家看个乐呵就行

KSroido Oct 12, 2023 — with giscus

改完的版本就懒得放出来了

KSroido Oct 12, 2023 — with giscus

稍微改了一下

#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();

}

Zjp-hub · 2023-10-12T05:02:14Z

Zjp-hub
Oct 12, 2023

已收到

0 replies

BoshLi · 2023-11-09T09:36:44Z

BoshLi
Nov 9, 2023 — with giscus

如果要删除中间元素是怎么操作的？

0 replies

Zjp-hub · 2023-11-09T09:37:08Z

Zjp-hub
Nov 9, 2023

已收到

0 replies

larry0442 · 2024-01-29T08:11:32Z

larry0442
Jan 29, 2024 — with giscus

之前实现过一个

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;
            }
        }
    }
}

0 replies

Zjp-hub · 2024-01-29T08:11:58Z

Zjp-hub
Jan 29, 2024

已收到

0 replies

二叉堆详解实现优先级队列 :: labuladong的算法小抄 #1039

Replies: 29 comments · 7 replies

GoingMyWay Nov 19, 2022 — with giscus

shiboys Sep 12, 2023 — with giscus

labuladong Oct 25, 2021 Maintainer

labuladong Mar 2, 2022 Maintainer

可设置比较函数最终版：

chloepei867 Nov 11, 2022 — with giscus

Youareblind Dec 1, 2022 — with giscus

Youareblind Dec 1, 2022 — with giscus

acmu Jan 1, 2023 — with giscus

bruceeewong Mar 6, 2023 — with giscus

marmot-z May 23, 2023 — with giscus

marmot-z May 24, 2023 — with giscus

marmot-z May 24, 2023 — with giscus

Zjp-hub Aug 22, 2023 — with giscus

shiboys Sep 17, 2023 — with giscus

KSroido Oct 12, 2023 — with giscus

KSroido Oct 12, 2023 — with giscus

KSroido Oct 12, 2023 — with giscus

KSroido Oct 12, 2023 — with giscus

BoshLi Nov 9, 2023 — with giscus

larry0442 Jan 29, 2024 — with giscus

Replies: 29 comments 7 replies

labuladong
Oct 25, 2021
Maintainer

labuladong
Mar 2, 2022
Maintainer

chloepei867
Nov 11, 2022 — with giscus

Youareblind
Dec 1, 2022 — with giscus

Youareblind
Dec 1, 2022 — with giscus

acmu
Jan 1, 2023 — with giscus

bruceeewong
Mar 6, 2023 — with giscus

marmot-z
May 23, 2023 — with giscus

Zjp-hub
Aug 22, 2023 — with giscus

shiboys
Sep 17, 2023 — with giscus

KSroido
Oct 12, 2023 — with giscus

BoshLi
Nov 9, 2023 — with giscus

larry0442
Jan 29, 2024 — with giscus