优先队列如何通过堆或左高树实现？
- 内容介绍
- 文章标签
- 相关推荐
本文共计2391个文字，预计阅读时间需要10分钟。
%E4%BC%AA%E5%88%9B%E4%BB%A5%E4%B8%8B%E5%BC%80%E5%A4%B4%E5%86%85%E5%AE%B9%E7%AE%80%E5%8D%95%E8%BD%AC%E5%86%99%E3%80%81%E6%9C%AA%E6%95%B0%E5%97%A6%E3%80%81%E4%B8%8D%E8%B6%85%E8%BF%87100%E5%AD%97%E3%80%81%E7%9B%B4%E6%8E%A5%E8%BE%93%E5%87%BA%E7%BB%93%E6%9E%9C%EF%BC%9A
%E4%BC%98%E5%85%88%E7%BA%A7%E9%98%9F%E5%88%97%EF%BC%8C%E6%98%AF%E4%B8%80%E4%B8%AA%E6%88%96%E5%A4%9A%E4%B8%AA%E5%85%83%E7%B4%A0%E7%9A%84%E9%9B%86%E5%90%88%EF%BC%8C%E6%AF%8F%E4%B8%AA%E5%85%83%E7%B4%A0%E9%83%BD%E6%9C%89%E4%B8%80%E4%B8%AA%E4%BC%98%E5%85%88%E7%BA%A7%EF%BC%88%E6%9D%83%E5%80%BC%EF%BC%89%E3%80%82
%E4%BC%98%E5%85%88%E7%BA%A7%E9%98%9F%E5%88%97%E7%9A%84%E5%8E%9F%E5%88%99%E5%8F%8A%E6%93%8D%E4%BD%9C%EF%BC%9A
1. top - 返回并移除队列中最大元素
2.push - 向队列中添加元素
3.pop - 从队列中移除元素
优先级队列堆优先级队列 (Priority Queue) 是0个或多个元素的集合，每个元素都有一个优先级 (权值)。
优先级队列的操作有：1. top 2. push 3. pop
在最大优先级队列中，查找和删除的元素都是当前集合中优先级最大的元素。
在最小优先级队列中，查找和删除的元素都是当前集合中优先级最小的元素。
(对于优先级相同的元素，其出队的顺序是未知的)
- 堆的性质：
- 堆是一颗完全二叉树
- 堆是一个大根树 (小根树)，父节点的优先级 大于 (小于) 或等于其子节点
- n个元素的堆的高度为 \(\lceil log_{2}(n + 1)\rceil\) ，在 \(O(height)\) 时间内可以完成插入和删除操作
- 堆的代码实现 (自己写的easy版)
#include <vector>
using std::vector;
using std::less;
// 默认容器是vector，默认仿函数是less(大根堆)
// 满足堆中所有元素都和堆顶保持比较谓词的关系 less or greater
template<class T, class _Container=vector<T>, class _Compare=less<T>>
class myHeap
{
protected:
_Container c;
_Compare cmp;
public:
myHeap() {}
// 避免不必要的隐式类型转换
explicit myHeap(const _Compare& x) : cmp(x) {}
size_t size() { return c.size(); }
bool empty() { return !c.size(); }
T top() { return c.front(); }
// 堆中插入元素，在堆底插入然后向上调整即可
void push(const T& element)
{
c.push_back(element);
if(size() > 1) up(c.size() - 1);
}
// 删除堆顶，由于线性表移动元素的时间开销较大
// 所以将堆顶和最后一个元素交换，然后尾删，对新堆顶向下调整
void pop()
{
if (size() >= 2)
{
heapSwap(0, c.size() - 1);
c.pop_back();
down(0);
}
else c.clear();
}
// 从其他容器建堆
template<class Iterator>
void makeHeap(Iterator first, Iterator end)
{
int len = end - first;
if (len < 2) return;
c.clear();
for (auto cur = first; cur != end; cur++)
c.push_back(*cur);
for (int root = (c.size() - 2) / 2; root >= 0; root--)
down(root);
}
private:
// 根据下标交换两个元素
void heapSwap(const int idxA, const int idxB)
{
T tmp = c[idxA];
c[idxA] = c[idxB];
c[idxB] = tmp;
}
// 元素向上调整
void up(const int idx)
{
int parent = (idx - 1) / 2;
int son = idx;
while (parent >= 0)
{
if (cmp(c[parent], c[son]))
{
heapSwap(son, parent);
son = parent;
parent = (son - 1) / 2;
}
else break;
}
}
// 元素向下调整
void down(const int idx)
{
// 获取父节点、左孩子、右孩子中优先级最高的
int cur = idx, left = idx * 2 + 1, right = idx * 2 + 2;
if (left < c.size() && cmp(c[cur], c[left]))
cur = left;
if (right < c.size() && cmp(c[cur], c[right]))
cur = right;
// 如果优先级最高的时某个子节点，则交换元素后进行递归
if (cur != idx)
{
heapSwap(cur, idx);
down(cur);
}
}
};
-
时间复杂度分析：
-
push最坏情况下，插入的元素是最大的，需要沿着树枝一路向上，每次递归的复杂度是 \(O(1)\)，递归深度是 \(logn\)，总时间复杂度为 \(O(logn)\) -
pop交换堆顶和最后一个元素时间复杂度为 \(O(1)\)，将堆顶向下调整最坏时间复杂度为 \(O(logn)\)，总时间复杂度为 \(O(logn)\) -
top直接获取堆顶，也就是第一个元素，时间复杂度为 \(O(1)\) -
makeHeap从其他容器建堆，while循环每一次down的时间为 \(O(h_{i})\)，\(h_{i}\) 是以 \(i\) 为根的树的高度，在完全二叉树中为 \(\lceil log_{2}(i + 1) \rceil\)，在第 \(j\) 层最多有 \(2^{j - 1}\) 个节点。可以推导出时间复杂度：\(O(\sum_{j=0}^{h - 1}(2^{j - 1}(h - j + 1)) = O(\sum_{k=2}^hk2^{h-k})) = O(2^h\sum_{k=2}^h(k / 2 ^ k)) = O(2 ^ k) = O(n)\)
其中 \(\sum_{k=1}^m\frac{k}{2^k} = 2 - \frac{m + 2}{2 ^ m}\)
-
-
堆是一个隐式数据结构，其优点是空间利用效率高，但是多个优先队列合并时比较麻烦。
令 \(s(x)\) 为该节点，到以该点为根的子树中最近的一个叶子节点的距离 (如果有一个孩子节点为null，则为1)
\(s(x)\) 的递推式：\(s(x) = min(s(L), s(R)) + 1\)
- 左高树是一个二叉树
- 左高树中，每一个内部节点满足 \(s(左孩子) >= s(右孩子)\)
- 如果这个条件是 左孩子的权重 >= 右孩子的权重，那么这棵树被称为 WBLT
- 如果HBLT同时也是一个大根树，则其称为最大HLBT；如果是小根数则是最小HBLT
定理：
- 以\(x\)为根的子树节点数目至少为 \(2^{s(x)} - 1\)
- 以\(x\)为根的子树有\(m\)个节点时，\(s(x)\) 最大为 \(log_2(m + 1)\)
- 从\(x\)到一个外部节点的最右路径的长度为 \(s(x)\)
- 代码实现
#include <queue>
using std::pair;
using std::queue;
using std::less;
// 二叉树节点
template <class T>
struct binaryTreeNode
{
// T在HBLT中一般是pair，first和second一般用于保存s(x)和元素
T element;
binaryTreeNode<T>* leftChild, * rightChild;
binaryTreeNode() { leftChild = rightChild = nullptr; }
binaryTreeNode(const T& theElement) : element(theElement) { leftChild = rightChild = nullptr; }
binaryTreeNode(const T& theElement, binaryTreeNode* theLeftChild, binaryTreeNode* theRightChild) :
element(theElement), leftChild(theLeftChild), rightChild(theRightChild) {}
};
// 默认仿函数是less(最大HBLT)
template <class T, class _Compare = less<T>>
class HBLT
{
public:
HBLT() { root = nullptr; treeSize = 0; }
explicit HBLT(const _Compare& x) : cmp(x) {}
void push(const T& theElement);
void pop();
T top() const { return root->element.second; }
void merge(HBLT<T>& theHBLT);
template<class Iterator>
void makeHBLT(Iterator begin, Iterator end);
private:
void merge(binaryTreeNode<pair<int, T>>*& a, binaryTreeNode<pair<int, T>>*& b);
binaryTreeNode<pair<int, T>>* root;
int treeSize;
_Compare cmp;
};
template <class T, class _Compare>
void HBLT<T, _Compare>::merge(binaryTreeNode<pair<int, T>>*& a, binaryTreeNode<pair<int, T>>*& b)
{
// 将b树合并到a树上，并以a的根为最后的根
if (b == nullptr) return;
if (a == nullptr) { a = b; return; }
// 按照仿函数堆根的值进行修改
if (cmp(a->element.second, b->element.second))
swap(a, b);
// 按照 a 的最右路径，将 b 树合并到 a 树的右子树上
merge(a->rightChild, b);
// 如果 a 的左子树为空，则将 b 树移到 a 的左子树，此时 a 的右子树一定非空
if (a->leftChild == nullptr)
{
a->leftChild = a->rightChild;
a->rightChild = nullptr;
// a 到最近的空叶子结点的距离很显然就是到右子树的距离 1
a->element.first = 1;
}
else
{
// 将高度较高的树放到左侧
if (a->leftChild->element.first < a->rightChild->element.first)
swap(a->leftChild, a->rightChild);
a->element.first = a->rightChild->element.first + 1;
}
}
template <class T, class _Compare>
void HBLT<T, _Compare>::merge(HBLT<T>& theHBLT)
{
merge(root, theHBLT.root);
treeSize += theHBLT.treeSize;
theHBLT.root = nullptr;
theHBLT.treeSize = 0;
}
template <class T, class _Compare>
void HBLT<T, _Compare>::push(const T& theElement)
{
// 新建一个只有根节点的树，将其合并到 root 上
auto newNode = new binaryTreeNode<pair<int, T>>(pair<int, T>(1, theElement));
merge(root, newNode);
treeSize++;
}
template <class T, class _Compare>
void HBLT<T, _Compare>::pop()
{
if (root == nullptr)
return;
// 将 root 删除后，将 left 设置为 root, 并将 right 合并到 root 上
auto left = root->leftChild;
auto right = root->rightChild;
delete root;
root = left;
merge(root, right);
treeSize--;
}
template <class T, class _Compare>
template <class Iterator>
void HBLT<T, _Compare>::makeHBLT(Iterator begin, Iterator end)
{
queue<binaryTreeNode<pair<int, T>>*> q;
int theSize = end - begin;
// 每个元素创建为一个子树，后续两个两个进行合并操作
for(auto cur = begin; cur != end; cur ++)
q.push(new binaryTreeNode<pair<int, T>>(pair<int, T>(1, *cur)));
// 总共theSize个点，需要theSize-1次合并
for (int i = 1; i <= theSize - 1; ++i)
{
auto b = q.front(); q.pop();
auto c = q.front(); q.pop();
merge(b, c);
q.push(b);
}
if (theSize > 0)
root = q.front();
treeSize = theSize;
}
- 时间复杂度分析
merge需要对两个树的最右路径进行搜索，每棵树的最右路径的长度是 \(log_2{(m + 1)}\) 和 \(log_2{(n + 1)}\)，每次移动的时间复杂度为 \(O(1)\)，总时间复杂度为 \(O(log_2(n + m))\)top的时间复杂度为 \(O(1)\)makeHBLT的时间复杂度为 \(O(\frac{n}{2} + 2*\frac{n}{4} + 3 * \frac{n}{8} + \cdots) = O(n\sum\frac{i}{2^i}) = O(n)\)
- 左高树在多个优先队列合并时效率很高
本文共计2391个文字，预计阅读时间需要10分钟。
%E4%BC%AA%E5%88%9B%E4%BB%A5%E4%B8%8B%E5%BC%80%E5%A4%B4%E5%86%85%E5%AE%B9%E7%AE%80%E5%8D%95%E8%BD%AC%E5%86%99%E3%80%81%E6%9C%AA%E6%95%B0%E5%97%A6%E3%80%81%E4%B8%8D%E8%B6%85%E8%BF%87100%E5%AD%97%E3%80%81%E7%9B%B4%E6%8E%A5%E8%BE%93%E5%87%BA%E7%BB%93%E6%9E%9C%EF%BC%9A
%E4%BC%98%E5%85%88%E7%BA%A7%E9%98%9F%E5%88%97%EF%BC%8C%E6%98%AF%E4%B8%80%E4%B8%AA%E6%88%96%E5%A4%9A%E4%B8%AA%E5%85%83%E7%B4%A0%E7%9A%84%E9%9B%86%E5%90%88%EF%BC%8C%E6%AF%8F%E4%B8%AA%E5%85%83%E7%B4%A0%E9%83%BD%E6%9C%89%E4%B8%80%E4%B8%AA%E4%BC%98%E5%85%88%E7%BA%A7%EF%BC%88%E6%9D%83%E5%80%BC%EF%BC%89%E3%80%82
%E4%BC%98%E5%85%88%E7%BA%A7%E9%98%9F%E5%88%97%E7%9A%84%E5%8E%9F%E5%88%99%E5%8F%8A%E6%93%8D%E4%BD%9C%EF%BC%9A
1. top - 返回并移除队列中最大元素
2.push - 向队列中添加元素
3.pop - 从队列中移除元素
优先级队列堆优先级队列 (Priority Queue) 是0个或多个元素的集合，每个元素都有一个优先级 (权值)。
优先级队列的操作有：1. top 2. push 3. pop
在最大优先级队列中，查找和删除的元素都是当前集合中优先级最大的元素。
在最小优先级队列中，查找和删除的元素都是当前集合中优先级最小的元素。
(对于优先级相同的元素，其出队的顺序是未知的)
- 堆的性质：
- 堆是一颗完全二叉树
- 堆是一个大根树 (小根树)，父节点的优先级 大于 (小于) 或等于其子节点
- n个元素的堆的高度为 \(\lceil log_{2}(n + 1)\rceil\) ，在 \(O(height)\) 时间内可以完成插入和删除操作
- 堆的代码实现 (自己写的easy版)
#include <vector>
using std::vector;
using std::less;
// 默认容器是vector，默认仿函数是less(大根堆)
// 满足堆中所有元素都和堆顶保持比较谓词的关系 less or greater
template<class T, class _Container=vector<T>, class _Compare=less<T>>
class myHeap
{
protected:
_Container c;
_Compare cmp;
public:
myHeap() {}
// 避免不必要的隐式类型转换
explicit myHeap(const _Compare& x) : cmp(x) {}
size_t size() { return c.size(); }
bool empty() { return !c.size(); }
T top() { return c.front(); }
// 堆中插入元素，在堆底插入然后向上调整即可
void push(const T& element)
{
c.push_back(element);
if(size() > 1) up(c.size() - 1);
}
// 删除堆顶，由于线性表移动元素的时间开销较大
// 所以将堆顶和最后一个元素交换，然后尾删，对新堆顶向下调整
void pop()
{
if (size() >= 2)
{
heapSwap(0, c.size() - 1);
c.pop_back();
down(0);
}
else c.clear();
}
// 从其他容器建堆
template<class Iterator>
void makeHeap(Iterator first, Iterator end)
{
int len = end - first;
if (len < 2) return;
c.clear();
for (auto cur = first; cur != end; cur++)
c.push_back(*cur);
for (int root = (c.size() - 2) / 2; root >= 0; root--)
down(root);
}
private:
// 根据下标交换两个元素
void heapSwap(const int idxA, const int idxB)
{
T tmp = c[idxA];
c[idxA] = c[idxB];
c[idxB] = tmp;
}
// 元素向上调整
void up(const int idx)
{
int parent = (idx - 1) / 2;
int son = idx;
while (parent >= 0)
{
if (cmp(c[parent], c[son]))
{
heapSwap(son, parent);
son = parent;
parent = (son - 1) / 2;
}
else break;
}
}
// 元素向下调整
void down(const int idx)
{
// 获取父节点、左孩子、右孩子中优先级最高的
int cur = idx, left = idx * 2 + 1, right = idx * 2 + 2;
if (left < c.size() && cmp(c[cur], c[left]))
cur = left;
if (right < c.size() && cmp(c[cur], c[right]))
cur = right;
// 如果优先级最高的时某个子节点，则交换元素后进行递归
if (cur != idx)
{
heapSwap(cur, idx);
down(cur);
}
}
};
-
时间复杂度分析：
-
push最坏情况下，插入的元素是最大的，需要沿着树枝一路向上，每次递归的复杂度是 \(O(1)\)，递归深度是 \(logn\)，总时间复杂度为 \(O(logn)\) -
pop交换堆顶和最后一个元素时间复杂度为 \(O(1)\)，将堆顶向下调整最坏时间复杂度为 \(O(logn)\)，总时间复杂度为 \(O(logn)\) -
top直接获取堆顶，也就是第一个元素，时间复杂度为 \(O(1)\) -
makeHeap从其他容器建堆，while循环每一次down的时间为 \(O(h_{i})\)，\(h_{i}\) 是以 \(i\) 为根的树的高度，在完全二叉树中为 \(\lceil log_{2}(i + 1) \rceil\)，在第 \(j\) 层最多有 \(2^{j - 1}\) 个节点。可以推导出时间复杂度：\(O(\sum_{j=0}^{h - 1}(2^{j - 1}(h - j + 1)) = O(\sum_{k=2}^hk2^{h-k})) = O(2^h\sum_{k=2}^h(k / 2 ^ k)) = O(2 ^ k) = O(n)\)
其中 \(\sum_{k=1}^m\frac{k}{2^k} = 2 - \frac{m + 2}{2 ^ m}\)
-
-
堆是一个隐式数据结构，其优点是空间利用效率高，但是多个优先队列合并时比较麻烦。
令 \(s(x)\) 为该节点，到以该点为根的子树中最近的一个叶子节点的距离 (如果有一个孩子节点为null，则为1)
\(s(x)\) 的递推式：\(s(x) = min(s(L), s(R)) + 1\)
- 左高树是一个二叉树
- 左高树中，每一个内部节点满足 \(s(左孩子) >= s(右孩子)\)
- 如果这个条件是 左孩子的权重 >= 右孩子的权重，那么这棵树被称为 WBLT
- 如果HBLT同时也是一个大根树，则其称为最大HLBT；如果是小根数则是最小HBLT
定理：
- 以\(x\)为根的子树节点数目至少为 \(2^{s(x)} - 1\)
- 以\(x\)为根的子树有\(m\)个节点时，\(s(x)\) 最大为 \(log_2(m + 1)\)
- 从\(x\)到一个外部节点的最右路径的长度为 \(s(x)\)
- 代码实现
#include <queue>
using std::pair;
using std::queue;
using std::less;
// 二叉树节点
template <class T>
struct binaryTreeNode
{
// T在HBLT中一般是pair，first和second一般用于保存s(x)和元素
T element;
binaryTreeNode<T>* leftChild, * rightChild;
binaryTreeNode() { leftChild = rightChild = nullptr; }
binaryTreeNode(const T& theElement) : element(theElement) { leftChild = rightChild = nullptr; }
binaryTreeNode(const T& theElement, binaryTreeNode* theLeftChild, binaryTreeNode* theRightChild) :
element(theElement), leftChild(theLeftChild), rightChild(theRightChild) {}
};
// 默认仿函数是less(最大HBLT)
template <class T, class _Compare = less<T>>
class HBLT
{
public:
HBLT() { root = nullptr; treeSize = 0; }
explicit HBLT(const _Compare& x) : cmp(x) {}
void push(const T& theElement);
void pop();
T top() const { return root->element.second; }
void merge(HBLT<T>& theHBLT);
template<class Iterator>
void makeHBLT(Iterator begin, Iterator end);
private:
void merge(binaryTreeNode<pair<int, T>>*& a, binaryTreeNode<pair<int, T>>*& b);
binaryTreeNode<pair<int, T>>* root;
int treeSize;
_Compare cmp;
};
template <class T, class _Compare>
void HBLT<T, _Compare>::merge(binaryTreeNode<pair<int, T>>*& a, binaryTreeNode<pair<int, T>>*& b)
{
// 将b树合并到a树上，并以a的根为最后的根
if (b == nullptr) return;
if (a == nullptr) { a = b; return; }
// 按照仿函数堆根的值进行修改
if (cmp(a->element.second, b->element.second))
swap(a, b);
// 按照 a 的最右路径，将 b 树合并到 a 树的右子树上
merge(a->rightChild, b);
// 如果 a 的左子树为空，则将 b 树移到 a 的左子树，此时 a 的右子树一定非空
if (a->leftChild == nullptr)
{
a->leftChild = a->rightChild;
a->rightChild = nullptr;
// a 到最近的空叶子结点的距离很显然就是到右子树的距离 1
a->element.first = 1;
}
else
{
// 将高度较高的树放到左侧
if (a->leftChild->element.first < a->rightChild->element.first)
swap(a->leftChild, a->rightChild);
a->element.first = a->rightChild->element.first + 1;
}
}
template <class T, class _Compare>
void HBLT<T, _Compare>::merge(HBLT<T>& theHBLT)
{
merge(root, theHBLT.root);
treeSize += theHBLT.treeSize;
theHBLT.root = nullptr;
theHBLT.treeSize = 0;
}
template <class T, class _Compare>
void HBLT<T, _Compare>::push(const T& theElement)
{
// 新建一个只有根节点的树，将其合并到 root 上
auto newNode = new binaryTreeNode<pair<int, T>>(pair<int, T>(1, theElement));
merge(root, newNode);
treeSize++;
}
template <class T, class _Compare>
void HBLT<T, _Compare>::pop()
{
if (root == nullptr)
return;
// 将 root 删除后，将 left 设置为 root, 并将 right 合并到 root 上
auto left = root->leftChild;
auto right = root->rightChild;
delete root;
root = left;
merge(root, right);
treeSize--;
}
template <class T, class _Compare>
template <class Iterator>
void HBLT<T, _Compare>::makeHBLT(Iterator begin, Iterator end)
{
queue<binaryTreeNode<pair<int, T>>*> q;
int theSize = end - begin;
// 每个元素创建为一个子树，后续两个两个进行合并操作
for(auto cur = begin; cur != end; cur ++)
q.push(new binaryTreeNode<pair<int, T>>(pair<int, T>(1, *cur)));
// 总共theSize个点，需要theSize-1次合并
for (int i = 1; i <= theSize - 1; ++i)
{
auto b = q.front(); q.pop();
auto c = q.front(); q.pop();
merge(b, c);
q.push(b);
}
if (theSize > 0)
root = q.front();
treeSize = theSize;
}
- 时间复杂度分析
merge需要对两个树的最右路径进行搜索，每棵树的最右路径的长度是 \(log_2{(m + 1)}\) 和 \(log_2{(n + 1)}\)，每次移动的时间复杂度为 \(O(1)\)，总时间复杂度为 \(O(log_2(n + m))\)top的时间复杂度为 \(O(1)\)makeHBLT的时间复杂度为 \(O(\frac{n}{2} + 2*\frac{n}{4} + 3 * \frac{n}{8} + \cdots) = O(n\sum\frac{i}{2^i}) = O(n)\)
- 左高树在多个优先队列合并时效率很高