优先队列（堆、左高树）

优先级队列 (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

定理：

1. 以\(x\)为根的子树节点数目至少为 \(2^{s(x)} - 1\)
2. 以\(x\)为根的子树有\(m\)个节点时，\(s(x)\) 最大为 \(log_2(m + 1)\)
3. 从\(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)\)
• 左高树在多个优先队列合并时效率很高