Project 8 — 优先队列 (Priority Queue)

100次阅读
没有评论

本项目实现了一个特殊的优先队列 (Priority Queue)。

为了帮助理解，这份文档将详细讲解每一个实现细节，从数据结构的设计到核心算法的逻辑。

1. 什么是优先队列？

普通的队列是“先进先出”（First-In, First-Out），就像排队买票一样。
而优先队列则不同，它像是一个VIP通道：无论你什么时候来，只要你的“优先级”最高（在本项目中，数值越小优先级越高），你就能最先出去。

本项目使用最小堆 (Min-Heap) 来实现这个功能。这意味着：

  • 根节点（最上面的节点）永远是所有数据中最小的。
  • 任何一个父节点的值都小于或等于它的子节点。

2. 本项目的特殊之处：从右向左生长

通常的二叉树是从左向右填满每一层的。但本项目有一个特殊要求：树必须从右向左生长 (Grow from Right to Left)。

这意味着：

  • 第 1 个节点是根节点。
  • 第 2 个节点是根的右孩子。
  • 第 3 个节点是根的左孩子。
  • 第 4 个节点是第 2 个节点的右孩子。
  • …以此类推。

3. 核心实现细节

3.1 数据结构设计 (Node.h)

我们将节点结构单独放在 Node.h 中，使用模板以支持不同类型的数据。为了更好的封装性，我们使用 class 并将数据设为私有，同时声明 PQ 为友元类。

// 前向声明 PQ 类
template <typename T> class PQ;

template <typename T>
class Node {
    // 声明 PQ 为友元，允许其访问私有成员
    friend class PQ
<T>;

private:
    T value;       // 存储的数据（如 int, double）
    Node
<T>* parent;  // 指向父节点
    Node
<T>* left;    // 指向左孩子
    Node
<T>* right;   // 指向右孩子

public:
    Node(T v) : value(v), parent(nullptr), left(nullptr), right(nullptr) {}
};

3.2 如何找到第 N 个节点？ (getNode 函数)

由于没有数组下标，我们需要一种方法来找到树中的第 N 个位置。我们利用了二进制的特性。

算法逻辑：

  1. 将 N 写成二进制。
  2. 忽略最高位的 1（它代表根节点）。
  3. 从高位到低位读取剩下的位：
    • 如果是 0 -> 向右走 (Right)。
    • 如果是 1 -> 向左走 (Left)。

例子 (查找第 5 个节点)：

  • 5 的二进制是 101。
  • 忽略最高位 1，剩下 01。
  • 第一步 0：从根节点向右走。
  • 第二步 1：从当前节点向左走。
  • 到达目标！

3.3 入队操作 (push)

当我们插入一个新元素时：

  1. 放置：根据当前的节点总数 (count)，找到下一个空闲位置（利用 getNode 找到父节点）。
    • 如果当前总数是偶数，新节点将成为右孩子。
    • 如果当前总数是奇数，新节点将成为左孩子。
  2. 上浮 (Bubble Up)：新加入的元素可能比它的父节点还小，破坏了“最小堆”的规则。
    • 我们不断比较它和父节点的值。
    • 如果它比父节点小，就交换它们的值。
    • 重复直到它比父节点大，或者到达根节点。

3.4 出队操作 (pop)

当我们取出最小元素（根节点）时：

  1. 保存：先记下根节点的值，准备最后返回。
  2. 替换：将堆中最后一个节点的值复制到根节点。
  3. 删除：删除最后一个节点，节点总数减 1。
  4. 下沉 (Bubble Down)：现在的根节点可能太大了，破坏了规则。
    • 找到它的两个孩子中较小的那一个。
    • 如果它比最小的孩子大，就交换它们。
    • 重复直到它比两个孩子都小，或者没有孩子。

4. 如何编译和运行

本项目包含一个 makefile，可以自动完成编译工作。

步骤 1：编译

在终端中输入以下命令并回车：

make

这会生成一个名为 main 的可执行文件。

步骤 2：运行

输入以下命令运行程序：

./main

步骤 3：清理

运行完毕后，可以使用以下命令清理生成的文件：

make clean

5. 项目完整代码

本项目仅用于交流学习，请按课程与学校规定提交作业。

为了方便学习，以下是本项目所有文件的完整代码。

点击此处可直接将项目压缩包下载到本地。

📄 Node.h (节点结构)

#ifndef NODE_H
#define NODE_H

#include 
<iostream>

using namespace std;

// 前向声明 PQ 类，以便在 Node 中将其声明为友元
template <typename T> class PQ;

template <typename T>
class Node {
    // 声明 PQ
<T> 为友元类，这样 PQ 就可以访问 Node 的私有成员
    friend class PQ
<T>;

private:
    T value;
    Node
<T>* parent;
    Node
<T>* left;
    Node
<T>* right;

public:
    // 构造函数
    Node(T v) : value(v), parent(nullptr), left(nullptr), right(nullptr) {}
};

#endif

📄 PQ.h (优先队列类与实现)

#ifndef PQ_H
#define PQ_H

#include 
<iostream>
#include 
<algorithm>
#include 
<stdexcept>
#include "Node.h"

using namespace std;

template <typename T>
class PQ {
private:
    Node
<T>* head;
    Node
<T>* tail;
    int count;

    Node
<T>* getNode(int n);
    void bubbleUp(Node
<T>* node);
    void bubbleDown(Node
<T>* node);

public:
    PQ();
    ~PQ();

    bool empty() const;
    int size() const;
    void push(T value);
    T pop();
};

// Implementation

template <typename T>
Node
<T>* PQ<T>::getNode(int n) {
    if (n <= 0 || n > count) return nullptr;
    if (n == 1) return head;

    // 计算最高位的位置（不包括根的最高位），然后从高位到低位依次检查位
    int temp = n;
    int msb = 0; // msb 为从根到目标需要的步数
    while (temp > 1) {
        temp /= 2;
        msb++;
    }

    Node
<T>* curr = head;
    for (int i = msb - 1; i >= 0; --i) {
        int bit = (n >> i) & 1; // 0 -> right, 1 -> left
        if (bit == 0) {
            curr = curr->right;
        } else {
            curr = curr->left;
        }
        if (!curr) return nullptr;
    }
    return curr;
}

template <typename T>
void PQ
<T>::bubbleUp(Node<T>* node) {
    while (node->parent && node->value < node->parent->value) {
        swap(node->value, node->parent->value);
        node = node->parent;
    }
}

template <typename T>
void PQ
<T>::bubbleDown(Node<T>* node) {
    while (true) {
        Node
<T>* smallest = node;
        // Check Right child first as per structure preference? 
        // Order doesn't strictly matter for correctness of MinHeap, 
        // but we should check both children.
        if (node->right && node->right->value < smallest->value) {
            smallest = node->right;
        }
        if (node->left && node->left->value < smallest->value) {
            smallest = node->left;
        }

        if (smallest != node) {
            swap(node->value, smallest->value);
            node = smallest;
        } else {
            break;
        }
    }
}

template <typename T>
PQ
<T>::PQ() : head(nullptr), tail(nullptr), count(0) {}

template <typename T>
PQ
<T>::~PQ() {
    while (!empty()) {
        pop();
    }
}

template <typename T>
bool PQ
<T>::empty() const {
    return count == 0;
}

template <typename T>
int PQ
<T>::size() const {
    return count;
}

template <typename T>
void PQ
<T>::push(T value) {
    Node
<T>* newNode = new Node<T>(value);
    if (count == 0) {
        head = tail = newNode;
        count++;
        return;
    }

    count++;
    Node
<T>* parent = getNode(count / 2);

    newNode->parent = parent;
    // Even -> Right child (0), Odd -> Left child (1)
    if (count % 2 == 0) {
        parent->right = newNode;
    } else {
        parent->left = newNode;
    }

    tail = newNode;
    bubbleUp(tail);
}

template <typename T>
T PQ
<T>::pop() {
    if (empty()) {
        throw runtime_error("PQ is empty");
    }

    T ret = head->value;

    if (count == 1) {
        delete head;
        head = tail = nullptr;
        count = 0;
        return ret;
    }

    head->value = tail->value;

    Node
<T>* oldTail = tail;
    Node
<T>* parent = oldTail->parent;

    if (parent) {
        if (parent->right == oldTail) parent->right = nullptr;
        else parent->left = nullptr;
    }

    delete oldTail;
    count--;

    tail = getNode(count);
    bubbleDown(head);

    return ret;
}

#endif

📄 main.C (测试文件)

#include 
<iostream>
#include "PQ.h"

using namespace std;

int main() {
    cout << "Testing PQ with int:" << endl;
    PQ
<int> pqInt;
    // Test case from slides: 3, 19, 2, 36, 17, 8, 7, 1
    // Expected pop order (Min Heap): 1, 2, 3, 7, 8, 17, 19, 36

    cout << "Pushing: 3, 19, 2, 36, 17, 8, 7, 1" << endl;
    pqInt.push(3);
    pqInt.push(19);
    pqInt.push(2);
    pqInt.push(36);
    pqInt.push(17);
    pqInt.push(8);
    pqInt.push(7);
    pqInt.push(1);

    cout << "Popping: ";
    while (!pqInt.empty()) {
        cout << pqInt.pop() << " ";
    }
    cout << endl;

    cout << "\nTesting PQ with double:" << endl;
    PQ
<double> pqDouble;
    cout << "Pushing: 3.5, 19.2, 2.1, 36.8, 17.4" << endl;
    pqDouble.push(3.5);
    pqDouble.push(19.2);
    pqDouble.push(2.1);
    pqDouble.push(36.8);
    pqDouble.push(17.4);

    cout << "Popping: ";
    while (!pqDouble.empty()) {
        cout << pqDouble.pop() << " ";
    }
    cout << endl;

    return 0;
}

📄 makefile (构建脚本)

all: main

CXX := g++
CXXFLAGS := -std=c++11 -Wall -Wextra -O2
DBGFLAGS := -std=c++11 -Wall -Wextra -g -O0

main: main.C PQ.h Node.h
    $(CXX) $(CXXFLAGS) -o main main.C

# Build a debug version (with symbols, no optimization) suitable for valgrind/asan
debug: CXXFLAGS := $(DBGFLAGS)
debug: clean
debug: main

# Run valgrind (requires valgrind installed on the system).
# This target depends on the debug build so symbols are available.
valgrind: debug
    valgrind --leak-check=full --show-leak-kinds=all --track-origins=yes ./main

run: main
    ./main

clean:
    rm -f main

正文完
C++ Queue
发表至： C++
2025年12月12日
 0
评论（没有评论）
文章搜索
YanQS
YanQS
分享技术，记录生活
文章数
29
阅读量
4647

YanQS's Blog

文章搜索
YanQS
YanQS
分享技术，记录生活
文章数
29
阅读量
4647

WordPress 用户评论回复邮件通知

Project 10 — 终端海战游戏 (Terminal Naval War Game)

Project 7 — Class BigInt

Project 9 — 农场生态模拟系统 (Farm Ecosystem Simulator)

Project 8 — 优先队列 (Priority Queue)