算法

堆

定义

满足以下条件的数据结构：

  • 完全二叉树 (:LiLink: 树 )
  • 子节点键值 都 $\le$ 或者 $\ge$ 父节点键值
分类

大/小根堆：

二叉堆

定义

同时满足以下条件：

  • 是 堆
  • 是 完全二叉树

用途

主要用于随时 $O(1)$ 查询最值。

实现

调整策略

调整策略分为两种 (大根堆)：

  • 向上调整 
    1
2
3
4
5
6

    auto heap::up(ID x) -> void {
	while(x > 0 && h[x / 2] < h[x]) {
		std::swap(h[x / 2], h[x]);
		x /= 2;
	}
}
  • 向下调整 
     1
 2
 3
 4
 5
 6
 7
 8
 9
10

    auto heap::down(ID x) -> void {
	while(x * 2 < size) {
		auto child = x * 2;
		if (child + 1 < size && h[child + 1] > h[child]) 
			child = child + 1;
		if (h[child] <= h[x]) break;
		std::swap(h[child], h[x]);
		x = child;
	}
}

插入

  1. 在最下层的最右侧插入
  2. 向上调整 时间复杂度 $O(\log{n})$。
1
2
3
4

auto Heap::push(T&& val) {
	h[++size] = std::move(val);
	up(size);
}

删除

  1. 将根节点与最后一个叶节点交换
  2. 交换厚的根节点向下调整 时间复杂度 $O(\log{n})$。
1
2
3
4

auto Heap::pop() -> void {
	std::swap(h[1], h[size]);
	down(1);
}

建堆

  • TODO：继续学习建堆
Note

你完全可以使用 STL 中的 std::priority_queue 作为堆。 其中：

  • 大根堆：std::priority_queue<T> (默认)
  • 小根堆：std::priority_queue<T, std::vector<T>, std::greater<T>>

对顶堆

定义

由一个大根堆和小根堆构成。

以 第 $k$ 大 问题为例：

  • 小根堆维护 前 $k$ 大元素，于是保证其堆顶是 第 $k$ 大元素。
  • 大根堆维护其余剩余元素。 只需要一直维持小根堆的 size 是 $k$ 即可。

用途

解决 top-n 问题。

实现

以 第 $k$ 大 问题为例。

整体而言，对顶堆支持以下操作：

  • 维护 ::update()：将小根堆 size 保持在 $k$
    • 小根堆 size 过大 $\Rightarrow$ 往大根堆塞
    • 小根堆 size 过小 $\Rightarrow$ 从大根堆取
  • 插入元素 ::push()：
    1. 先插入元素
      • 元素 $\ge$ 小根堆.top() $\Rightarrow$ 插入小根堆
      • 元素 $\lt$ 小根堆.top() $\Rightarrow$ 插入大根堆
    2. 维护队列 ::update()
  • 查询第 $k$ 大元素 ::top()：返回小根堆堆顶
  • 删除第 $k$ 大元素 ::pop()：先 pop 小根堆堆顶，再 ::update()
  • 更改第 $k$ 大元素

结构 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

// 大根堆
template<typename T>
using MinHeap = std::priority_queue<T>;
// 小根堆
template<typename T>
using MaxHeap = std::priority_queue<T, std::vector<T>, std::greater<T>>;

// 第k大对顶堆
template<typename T>
struct Heap {
	MinHeap<T> minh;
	MaxHeap<T> maxh;
	std::size_t top_n = 1; // 退化为朴素堆
};

维护 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

auto Heap::update() -> void {
    while (maxh.size() < top_n && !minh.empty()) {
	    maxh.push(minh.top());
	    minh.pop();
    }
    while (maxh.size() > top_n) {
	    minh.push(maxh.top());
	    maxh.pop();
    }
}

插入 

1
2
3
4
5
6
7
8
9

auto Heap::push(T&& val) -> void {
	if (maxh.empty() || val>=maxh.top()) {
		maxh.push(std::move(val));
		update();
	} else {
		minh.push(std::move(val));
		update();
	}
}

查询 

1

auto Heap::top() const -> const T& { return maxh.top(); }

配对堆

  • TODO：学习偏对堆

左偏树

  • TODO：学习左偏树