Try   HackMD

【資工考研】DS: Binary Tree (1) Binary Tree + Binary Search Tree + Heap

Tree Basic Definition

  • 不可為空 (node 數 \(\gt 0\))
  • 至少一個特定節點稱為 root
  • 其餘的節點可分為 \(k\) 個集合 (\(T_1,T_2,\cdots ,T_k\)) 稱為 subtree of a root
  • subtree 本身沒有方向性

Tree Representations

  1. linked list
  2. transform into the binary tree
  3. child-sibling
  4. parentheses

如何表示一棵樹呢？有上述四種方法，不過這邊我們只細談第一種

假設有下面這棵樹：







linked_list

Use the Linked List to Represent a Tree


A

A



B

B



A--B




C

C



A--C




D

D



A--D




E

E



C--E




F

F



C--F

我們可以這樣表示樹的節點，然後連接節點







structure



A

A

 

 

 

 



B

B

 

 

 

 



A:ref1->B





C

C

 

 

 

 



A:ref2->C





D

D

 

 

 

 



A:ref3->D





E

E

 

 

 

 



C:ref1->E





F

F

 

 

 

 



C:ref2->F

使用 C++ 表示節點結構的話：

template<typename T>
struct TreeNode
{
    T data;
    TreeNode *child1;
    TreeNode *child2;
    TreeNode *child3;
    TreeNode *child4;
};

你會注意到，當 tree 的 degree 最大為 \(k\) 時，我們就要讓每個節點都準備 \(k\) 條 links 的空間
如果有 \(n\) 個節點，那就需要 \(k\cdot n\) 條 links
但是根據 tree 本身的數學性質我們知道，非空 links 數只會有 \(n-1\) 條
因此，這個方法的空間浪費率為 \(\frac{nk-(n-1)}{nk}\)，大概是 \(\frac{k-1}{k}\)

如果 \(k=1\) 就退化成普通的 linked list 了我們就不討論，所以對 tree 來說 \(k=2\) 時浪費率最低，但也達到約 \(50\%\)

不過這個表示方法很直觀，而且表達 tree 上較有彈性
所以在表達 binary tree (也就是 \(k = 2\)) 時，我們更習慣用這種方法

Binary Tree

我們可以簡單記得 binary tree 就是每個節點的 degree \(\le 2\) 的 tree
不過要提醒，在資料結構這邊，binary tree 與 tree 還有其他不同的地方，其實不能說 binary tree 是 tree

  1. binary tree 可以為空 (node 0 個)
  2. 有 root 及左右子樹 (這邊強調左右 表示其不同於樹 有左右方向之分)
  3. 左右子樹亦為 binary tree
Tree Binary Tree
Cannot be empty Can be empty
Node degree ≥ 0 0 ≤ Node degree ≤ 2
Subtrees have no specific order Subtrees are ordered as left and right

性質

假設定 root 所在的 level 為 \(1\)

  1. level \(i\) 有 \(2^{i-1}\) 個 nodes
  2. 高度為 \(h\) 的 binary tree 最多有 \(2^h-1\) 個 nodes 最少 \(h\) 個 nodes
  3. 若 \(n_d\) 表示 degree 為 \(d\) 的 nodes 總數， \(n_0 = n_2 + 1\)

種類

  • Skewed Binary Tree
    • \(n\) 節點高度為 \(n\) (root level \(=1\))
  • Full Binary Tree
    • 節點數最大化的 binary tree
  • Complete Binary Tree
    • 節點增長順序由上而下，同 level 由左而右
    • 如果高度為 \(h\) 則節點樹介於 \(2^{h-1}-1\) 到 \(2^h-1\)
    • 如果 root 的編號為 \(1\) 則 \(\mathrm{node}_i\) 的若有左右子點，其編號為 \(2i, 2i+1\)；若有父點，其編號為 \(\left[ \frac{i}{2} \right]\)
  • Strict Binary Tree
    • 不存在 degree 為 \(1\) 的節點

Caution

要注意的是離散在這邊的定義與資結有點不同

Binary Tree Traversal

  • preorder
  • inorder
  • postorder
  • level order

令 BT 如下：







bt



D

D



L

L



D--L




R

R



D--R

\(L\) 跟 \(R\) 代表左右子樹，\(D\) 代表該樹的 root 則遍歷順序：

Preorder Inorder Postorder
DLR LDR LRD

其實很好記：

  1. 先走左子樹再走右子樹
  2. \(D\) 在前就是 preorder ，在中間就是 inorder ，在後面就是 postorder

而 level order 就是 level 從上往下由左向右遍歷

例如給你下面的 BT







linked_list



A

A



B

B



A--B




C

C



A--C




D

D



B--D




E

E



B--E




F

F



C--F




G

G



C--G

則遍歷結果：

Preorder Inorder Postorder Level Order
ABDECFG DBEAFCG DEBFGCA ABCDEFG

如果今天反過來給你遍歷順序，那麼怎樣的組合能決定唯一的 BT 呢？

Inputs Can Determine the Unique BT?
inorder + {preorder, postorder, or level order} YES
preorder + postorder NO
level order + {preorder or postorder} NO
full BT + {preorder, inorder, postorder, level order} YES
complete BT + {preorder, inorder, postorder, level order} YES
BST + {preorder, postorder, level order} YES

使用 linked list 的方式來表示 tree node 則 BT 的遍歷怎麼寫呢？

下面是節點的結構

template <typename T>
struct TreeNode
{
    T data;
    TreeNode *left;
    TreeNode *right;
    TreeNode(const T &val) : data(val), left(nullptr), right(nullptr) {}
};

為了表達方便，我們使用 enum class 來表達要選擇哪一種遍歷方式

enum class Traversal
{
    PREORDER,
    INORDER,
    POSTORDER,
    LEVELORDER,
};

則以 preorder 為例，我們可以很輕易寫出其遞迴演算法：

template <typename Functor>
void preorder(TreeNode<T> *node, Functor func)
{
    if (!node)
        return;
    func(node);                  // D
    preorder(node->left, func);  // L
    preorder(node->right, func); // R
}

Tip

nullptr 視為 false ，所以 !root 為 true 的情況即 root == nullptr (空樹)

記得我們前面講的遍歷記憶法嗎？沒錯，只要記得 DLR 你就能輕鬆寫出 code 了！
同理，inorder 跟 postorder ：

template <typename Functor>
void inorder(TreeNode<T> *node, Functor func)
{
    if (!node)
        return;
    inorder(node->left, func);  // L
    func(node);                 // D
    inorder(node->right, func); // R
}

template <typename Functor>
void postorder(TreeNode<T> *node, Functor func)
{
    if (!node)
        return;
    postorder(node->left, func);  // L
    postorder(node->right, func); // R
    func(node);                   // D
}

至於 level order 用 BFS：

template <typename Functor>
void levelorder(TreeNode<T> *node, Functor func)
{
    if (!node)
        return;

    std::queue<TreeNode<T> *> q;
    q.push(node);

    while (!q.empty())
    {
        TreeNode<T> *curr = q.front();
        q.pop();

        func(curr);
        if (curr->left)
            q.push(curr->left);
        if (curr->right)
            q.push(curr->right);
    }
}

如此，我們便能簡單寫出一個列印 BT 的 method：

void printBT(const Traversal &policy)
{
    auto printFunc = [](TreeNode<T> *node)
    {
        std::cout << node->data << " ";
    };

    switch (policy)
    {
    case Traversal::PREORDER:
        preorder(root, printFunc);
        break;

    case Traversal::INORDER:
        inorder(root, printFunc);
        break;

    case Traversal::POSTORDER:
        postorder(root, printFunc);
        break;

    case Traversal::LEVELORDER:
        levelorder(root, printFunc);
        break;

    default:
        std::cerr << "Invalid traversal policy!\n";
        break;
    }

    std::cout << "\n";
}

測試一下







linked_list



A

A



B

B



A--B




D

D



A--D




NULL

NULL



B--NULL




C

C



B--C




E

E



D--E




F

F



D--F





int main()
{

    BinaryTree<char> bt;
    bt.root = new TreeNode('A');
    TreeNode<char> *node1 = new TreeNode('B');
    TreeNode<char> *node2 = new TreeNode('C');
    TreeNode<char> *node3 = new TreeNode('D');
    TreeNode<char> *node4 = new TreeNode('E');
    TreeNode<char> *node5 = new TreeNode('F');

    // Build the BT
    bt.root->left = node1;
    bt.root->right = node3;
    node1->right = node2;
    node3->left = node4;
    node3->right = node5;

    std::cout << "Preorder Traversal:\n";
    bt.printBT(Traversal::PREORDER);

    std::cout << "\nInorder Traversal:\n";
    bt.printBT(Traversal::INORDER);

    std::cout << "\nPostorder Traversal:\n";
    bt.printBT(Traversal::POSTORDER);

    std::cout << "\nLevel-order Traversal:\n";
    bt.printBT(Traversal::LEVELORDER);

    return 0;
}

image

一些 BT 有可能會考的應用題

判斷兩樹相等

friend bool operator==(const BinaryTree<T> &lhs, const BinaryTree<T> &rhs)
    {
        std::function<bool(TreeNode<T> *, TreeNode<T> *)> btEqual = [&](TreeNode<T> *a, TreeNode<T> *b)
        {
            if (!a && !b)
                return true;
            if (!a || !b)
                return false;
            return (a->data == b->data) && btEqual(a->left, b->left) && btEqual(a->right, b->right);
        };

        return btEqual(lhs.root, rhs.root);
    }

friend bool operator!=(const BinaryTree<T> &lhs, const BinaryTree<T> &rhs) { return !(lhs == rhs); }

複製 BT

TreeNode<T> *btCopy(TreeNode<T> *node)
{
    if (!node)
        return nullptr;

    TreeNode<T> *newNode = new TreeNode<T>(node->data);
    newNode->left = btCopy(node->left);
    newNode->right = btCopy(node->right);
    return newNode;
}

現在我們可以進一步補充我們的 constructor 跟 = operator

/**
* @brief Default constructor (empty tree)
*/
BinaryTree() noexcept : root{nullptr} {}
/**
* @brief Copy constructor
*/
BinaryTree(const BinaryTree<T> &other) noexcept : root(btCopy(other.root)) {}

/**
* @brief Move constructor
*/
BinaryTree(BinaryTree<T> &&other) noexcept : root(other.root) { other.root = nullptr; }

/**
* @brief Copy assigment operator
*/
BinaryTree<T> &operator=(const BinaryTree<T> &other)
{
    if (this != &other)
    {
        btDestroy();
        root = btCopy(other.root);
    }
    return *this;
}

/**
* @brief Move assignment operator
*/
BinaryTree<T> &operator=(BinaryTree<T> &&other) noexcept
{
    if (this != &other)
    {
        root = other.root;
        other.root = nullptr;
    }
    return *this;
}

Expression BT

可以想像是 compiler 建立 parsing tree or syntax tree 的作法

原則：

  1. leaf 表示 operand
  2. non-leaf 表示 operator
  3. 優先權大的鄰近 operator level 較大 (較下面)

例如給 a + b * c - d / e

把這想成是 BT inorder 的結果
則 postorder 為 abc * + de / -

只要有這兩個遍歷結果就能建構回樹了







linked_list



A

-



B

+



A--B




C

/



A--C




D

a



B--D




E

*



B--E




F

d



C--F




G

e



C--G




H

b



E--H




I

c



E--I

我覺得這邊只要會手寫作答的部份就好了

其他

這邊附上截止至本文撰寫時，本人印象中有解過，LeetCode 上跟 BT 有關的題目

Binary Search Tree

是 BT ，故可以為空
若不為空：

  • root 之左子樹上任意節點之值小於 root 之值
  • root 之右子樹上任意節點之值大於 root 之值
  • root 之左右子樹亦為 BST

Tip

BST 的 inorder traversal 必定是由小到大排列輸出

namespace riklib
{
    template <typename T>
    struct Iterator
    {
        using Node = TreeNode<T>;

        Node *curr;
        std::vector<Node *> ancestors;

        Iterator(Node *root = nullptr)
        {
            curr = root;
            // find smallest element in BST
            while (curr && curr->left)
            {
                ancestors.push_back(curr);
                curr = curr->left;
            }
        }

        T &operator*() const { return curr->data; }
        friend bool operator==(const Iterator &lhs, const Iterator &rhs) { return lhs.curr == rhs.curr; }
        friend bool operator!=(const Iterator &lhs, const Iterator &rhs) { return !(lhs == rhs); };
    };

    template <typename T>
    class BinarySearchTree : public BinaryTree<T>
    {
    public:
        using Node = TreeNode<T>;
        using iterator = Iterator<T>;

        BinarySearchTree() {}

        iterator begin() noexcept { return iterator(this->root); }
        iterator begin() const noexcept { return iterator(this->root); }
        iterator cbegin() const noexcept { return iterator(this->root); }

        iterator end() noexcept { return iterator(nullptr); }
        iterator end() const noexcept { return iterator(nullptr); }
        iterator cend() const noexcept { return iterator(nullptr); }
    };

} // namespace riklib

Inorder predecessor and successor

我們知道 BST 的 inorder 就是 sorted order
故 inorder successor 即 sorted order 中的下一位； inorder predecessor 同理為上一位
對應我們 Iterator 實作便是 ++ 跟 -- 運算

這邊我大致提供一個簡單的實作以供參考

我們給 TreeNode 增加 parent 指標
Iterator 更新後如下：

    template <typename T>
    struct Iterator
    {
        using Node = TreeNode<T>;

        Node *curr;

        Iterator(Node *root = nullptr)
        {
            curr = root;
            // find smallest element in BST
            while (curr && curr->left)
                curr = curr->left;
        }

        T &operator*() const { return curr->data; }
        friend bool operator==(const Iterator &lhs, const Iterator &rhs) { return lhs.curr == rhs.curr; }
        friend bool operator!=(const Iterator &lhs, const Iterator &rhs) { return !(lhs == rhs); };

        Iterator &operator++()
        {
            if (!curr)
                throw std::out_of_range("Iterator out of range");

            if (curr->right)
            {
                curr = curr->right;
                while (curr->left)
                    curr = curr->left;
            }
            else
            {
                Node *parent = curr->parent;
                while (parent && parent->right == curr)
                {
                    curr = parent;
                    parent = parent->parent;
                }
                curr = parent;
            }
            return *this;
        }

        Iterator operator++(int)
        {
            Iterator temp = *this;
            ++(*this);
            return temp;
        }

        Iterator &operator--()
        {
            if (!curr)
                throw std::out_of_range("Iterator out of range");

            if (curr->left)
            {
                curr = curr->left;
                while (curr->right)
                    curr = curr->right;
            }
            else
            {
                Node *parent = curr->parent;
                while (parent && parent->left == curr)
                {
                    curr = parent;
                    parent = parent->parent;
                }
                curr = parent;
            }
            return *this;
        }

        Iterator operator--(int)
        {
            Iterator temp = *this;
            --(*this);
            return temp;
        }

        Iterator operator+(int n) const
        {
            Iterator it = *this;
            for (int i = 0; i < n; ++i)
            {
                ++it;
            }
            return it;
        }

        Iterator operator-(int n) const
        {
            Iterator it = *this;
            for (int i = 0; i < n; ++i)
            {
                --it;
            }
            return it;
        }

        Iterator &operator+=(int n)
        {
            for (int i = 0; i < n; ++i)
                ++(*this);
            return *this;
        }

        Iterator &operator-=(int n)
        {
            for (int i = 0; i < n; ++i)
                --(*this);
            return *this;
        }
    };

Insert

我們就依照 BST 的規則找正確的位置放置新節點即可

多次 insert() 便可建立 BST
BST 建立之結構受 input 順序影響，如果給 sorted input 則會得 skewed BST

範例：

input: 5, 8, 9, 3, 1, 4, 6, 2, 7

image

        /**
         * @brief Insert a value into the BST.
         *
         * @param value The value to insert.
         * @return A pair containing an iterator to the inserted node (or the node
         *         with the same value) and a boolean indicating success.
         */
        std::pair<iterator, bool> insert(const T &val)
        {
            Node **curr = &this->root;
            Node *parent = nullptr;

            while (*curr)
            {
                parent = *curr;
                if (val == (*curr)->data)
                    // Value already exists in the BST
                    return {iterator(*curr), false};

                if (val < (*curr)->data)
                    curr = &(*curr)->left;
                else
                    curr = &(*curr)->right;
            }

            *curr = new Node(val);
            (*curr)->parent = parent;
            return {iterator(*curr), true};
        }

Delete

  1. 找到目標 x
  2. 分三種情況：
    1. x is leaf: 直接砍掉
    2. deg(x) == 1 把 x 的 parent 指向 x 的 child 再砍掉 x
    3. deg(x) == 2 找左子樹最大值 or 右子樹最小值 令為 y 以 y 取代 x 再 delete(y) (原本位置的 y)

例如原本的 BST

image

砍 5 ，假設採用左子樹最大值則過程：

image
image

        /**
         * @brief Erases the node at the given position in the BST.
         *
         * @param pos Iterator pointing to the node to erase. Must be a valid iterator
         *            obtained from this tree or its end iterator.
         * @return Iterator pointing to the next in-order node after the erased node.
         *         If the erased node was the last in-order node, returns end().
         */
        iterator erase(iterator pos)
        {
            if (!pos.curr)
                return end(); // Return end iterator if the position is invalid

            Node **parent_link = &this->root;
            Node *target = this->root;

            while (target && target != pos.curr)
            {
                if (pos.curr->data < target->data)
                    parent_link = &target->left, target = target->left;
                else
                    parent_link = &target->right, target = target->right;
            }

            if (!target)
                return end();

            // Case 1: Node is a leaf node
            if (!target->left && !target->right)
            {
                delete target;
                *parent_link = nullptr;
            }
            // Case 2: Node has only one child
            else if (!target->left || !target->right)
            {
                Node *child = target->left ? target->left : target->right;
                delete target;
                *parent_link = child;
                if (child)
                    child->parent = *parent_link;
            }
            // Case 3: Node has two child
            else
            {
                // Find the inorder successor (smallest node in the right subtree)
                Node **successor_link = &target->right;
                Node *successor = target->right;

                while (successor->left)
                    successor_link = &successor->left, successor = successor->left;

                // Replace target's value with successor's value
                target->data = successor->data;

                // Case 1 or 2 for the successor (successor->left must be nullptr now)
                *successor_link = successor->right;
                if (successor->right)
                    successor->right->parent = successor->parent;
                delete successor;
            }

            if (!this->root)
                return end();

            Node *next = nullptr;
            if (target->right)
            {
                next = target->right;
                while (next->left)
                    next = next->left;
            }
            else
            {
                Node *parent = target->parent;
                while (parent && parent->right == target)
                {
                    target = parent;
                    parent = parent->parent;
                }
                next = parent;
            }

            if (next == target)
                return begin();

            return iterator(next);
        }

因為普通 BST 的 insert() 相對簡單，所以對 iterator 的影響很好處理
但是 erase() 就不一樣了，我們要注意該操作對 iterator 有效性的破壞

下面是我大致 debug 用的 code：

#include "binary_search_tree.hpp"

using namespace riklib;

int main()
{
    BinarySearchTree<int> bst;
    bst.insert(4);
    bst.insert(1);
    bst.insert(0);
    bst.insert(3);
    bst.insert(2);

    bst.printBT(Traversal::PREORDER);

    for (auto it = bst.begin(); it != bst.end();)
    {
        it = bst.erase(it);
    }
    std::cout << (bst.root == nullptr) << "\n";
    bst.printBT(Traversal::PREORDER);

    return 0;
}

因為每次 erase() 會破壞 iterator 之有效性，所以我們要將 it 更新成 erase() 回傳的下個位置

image

有成功砍完整棵 BST ，最後 bst 變回了空樹

        /**
         * @brief Finds a node containing the given value in the BST.
         *
         * @param val The value to search for in the tree.
         * @return Iterator pointing to the node containing the value if found, or the end
         *         iterator if the value is not found.
         */
        iterator find(const T &val)
        {
            Node *curr = this->root;

            while (curr)
            {
                if (val == curr->data)
                    return iterator(curr);
                curr = val < curr->data ? curr->left : curr->right;
            }

            return end();
        }

看到這邊，相信各位算是基礎認識 BST 了
那各位會發現，best case 跟 average case 下 find() 的時間複雜度是 \(O(\lg n)\) 沒有什麼問題
但如果 BST 是 skewed tree 的話，就會有 worst case \(O(n)\)
insert() 跟 erase() 也跟 find() 一樣

這問題就是 BST 的高度並未受到控制，而都叫 binary search tree 了，find() 的時間複雜度我們肯定是希望能好點，不要退化到線性時間
在未來，我們將會討論高度平衡的 BST 來解決這問題

Find k-th smallest in BST

最直覺的方法當然是按照 inorder 等第 k 個出現
但我們有其他作法

關鍵是我們在多紀錄每個節點其左子樹的節點個數
如此一來我們便可以輕鬆找出第 k 小了

大致 pseudocode 長這樣：

FindKthSmallest(node, k)
    // node: the root of the current subtree
    // k: the rank of the smallest element to find
    let r ← node.left.size + 1  // Compute the rank of node within its subtree
    if k = r then
        return node            // node is the k-th smallest element
    else if k < r then
        return FindKthSmallest(node.left, k)  // Recur into the left subtree
    else
        return FindKthSmallest(node.right, k - r)  // Recur into the right subtree with adjusted rank

k == r 的 case 不必多說
k < r 時，表示要找的目標在當前根節點的左子樹裡；k > r 時，表示左子樹裡沒有想要的，前 r 個後面都不用看了，前 k 個少了 r 個，所以所求是剩下元素中前 k - r 小的那個

這個可以記一下大概演算法怎麼寫
不難，但經典

Heap

  • 為 complete BT
  • 以 Max-Heap 來說父點必大於其左右子點；Min-Heap 則小於
  • Root Max-Heap 為最大值 而 Min-Heap 為最小值

前面講過 complete BT 會發現這種 BT 其實節點長很滿
這種時候其實反而使用 array 保存更適合

Heap 可以用來製作 priority queue 也能用來 heap sort

Operations Time Complexity
Insert \(O(\lg n)\)
Delete-Max (Delete-Min) \(O(\lg n)\)
Heapifty \(O(\lg n)\)
Find-Max (Find-Min) \(O(1)\)
Build \(O(n)\)
Decrease key \(O(\lg n)\)
Merge \(O(n)\)

以下提供基礎的 binary heap 實作

namespace riklib
{
    // Defualt: Min-Heap
    template <typename T, typename Compare = std::less<T>>
    class BinaryHeap
    {
    private:
        std::vector<T> heap;
        Compare compare;

    public:
        using iterator = typename std::vector<T>::iterator;
        using const_iterator = typename std::vector<T>::const_iterator;

        BinaryHeap() noexcept = default;

        explicit BinaryHeap(const Compare &comp) : compare(comp) {}

        BinaryHeap(std::initializer_list<T> init, const Compare &comp = Compare()) : heap(init), compare(comp) { buildHeap(); }

        BinaryHeap(const BinaryHeap &other) = default;
        BinaryHeap(BinaryHeap &&other) noexcept = default;

        BinaryHeap &operator=(const BinaryHeap &other) = default;
        BinaryHeap &operator=(BinaryHeap &&other) noexcept = default;

        ~BinaryHeap() = default;

        iterator begin() noexcept { return heap.begin(); }
        const_iterator begin() const noexcept { return heap.begin(); }
        const_iterator cbegin() const noexcept { return heap.cbegin(); }

        iterator end() noexcept { return heap.end(); }
        const_iterator end() const noexcept { return heap.end(); }
        const_iterator cend() const noexcept { return heap.cend(); }

        /**
         * @brief Inserts a value into the heap while maintaining the heap property.
         * @param val The value to insert.
         */
        void push(const T &val)
        {
            heap.push_back(val);
            size_t idx = heap.size() - 1;

            while (idx > 0)
            {
                size_t parent = (idx - 1) / 2;

                if (compare(heap[idx], heap[parent]))
                {
                    std::swap(heap[idx], heap[parent]);
                    idx = parent;
                }
                else
                    break;
            }
        }

        /**
         * @brief Removes the top element from the heap.
         * @throw std::runtime_error if the heap is empty.
         */
        void pop()
        {
            if (heap.empty())
                throw std::runtime_error("Cannot pop from an empty heap.");

            std::swap(heap.front(), heap.back());
            heap.pop_back();
            if (!heap.empty())
                heapify(0);
        }

        /**
         * @brief Returns the top element of the heap.
         * @throws std::runtime_error if the heap is empty.
         * @return const T& The top element of the heap.
         */
        const T &top() const
        {
            if (heap.empty())
                throw std::runtime_error("Heap is empty.");

            return heap.front();
        }

        /**
         * @brief Checks if the heap is empty.
         * @return true if the heap is empty, false otherwise.
         */
        bool empty() const noexcept { return heap.empty(); }

        /**
         * @brief Returns the number of elements in the heap.
         * @return size_t The size of the heap.
         */
        size_t size() const noexcept { return heap.size(); }

    private:
        void heapify(size_t idx)
        {
            const size_t n = heap.size();
            size_t target = idx;
            size_t left = 2 * idx + 1;
            size_t right = 2 * idx + 2;

            if (left < n && compare(heap[left], heap[target]))
                target = left;
            if (right < n && compare(heap[right], heap[target]))
                target = right;

            if (target != idx)
            {
                std::swap(heap[idx], heap[target]);
                heapify(target);
            }
        }

        void buildHeap()
        {
            const size_t n = heap.size();
            for (size_t i = n / 2; i > 0; --i)
            {
                heapify(i - 1);
            }
        }
    };
}

build

我們有兩種方式來初始建構 heap：

  1. top-down
  2. bottom-up

top-down 很簡單，就是依照輸入順序一個個 push()(insert) 進去
可是這樣的時間複雜度其實是 \(O(n\lg n)\)

\[ \sum\limits_{i=1}^{n}\lg i = \lg (n!) = O(n\lg n) \]

另一種方式即 bottom-up
我們是先讓所有元素都放進 array (可以想成先填進 complete BT 中)
接著使用 heapify 的方式調整陣列使其符合 heap 的性質
這樣講有點抽象 具體來說就是從最後一個 parent 開始往上使每棵子樹皆符合 heap 性質直到 root
這樣的時間複雜度就是 \(O(n)\) 了

merge

/**
* @brief Merges another binary heap into this heap.
*        The merge operation maintains the heap property.
* @param other The other binary heap to merge with this heap.
*/
void merge(const BinaryHeap &other) noexcept
{
    heap.insert(heap.end(), other.heap.begin(), other.heap.end());
    buildHeap();
}

【資工考研】DS: Binary Tree 全系列

Last changed by 
 
RyoukiWei
0
41

Read more

DM Generating Function

1+x+\cdots +x^n = \frac{1-x^{n+1}}{1-x}

Feb 4, 2025
DSA Search & Sort

Linear (sequential) search

Feb 3, 2025
DM 遞迴關係式

考慮 a_0,a_1,\cdots ,a_n

Feb 2, 2025
DM 二元關係

考慮集合 A, B 之卡氏積 A\times B

Feb 1, 2025
Read more from RyoukiWei
Published on HackMD