二叉树

您所在的位置：网站首页 › 二叉堆实现优先队列 › 二叉树

二叉树

2023-12-10 09:41| 来源: 网络整理| 查看: 265

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

优先队列的c++实现前言一、定义二、代码实现头文件：PriorityQueue.h源文件：

前言

优先队列（堆）满足先进先出，而且每次出队的都是队列中最小的（也可以是最大的，看实现过程）。堆是一棵完全二叉树，所以优先队列一般用二叉堆实现。C++有自带的PriorityQueue，但是C#没有。所以写一下

一、定义

示例：pandas 是基于NumPy 的一种工具，该工具是为了解决数据分析任务而创建的。 1.一棵完全二叉树，所以可以用一个数组表示而不需要用指针。但是用数组就要事先估计堆的大小，所以用一个Capacity表示最大值；

2.因为保持堆序性质，最小元就是在根上，删除后还得做一些调整来保持完全二叉树的结构（实际就是删除最后一个元素，然后把它插入到队列中）;

3.若当前节点下标为i，则i2和i2+1就是它的左右孩子，我们在data[0]处放了一个MIN_INT;

4.入队：首先size++，如果data[size]插入不破坏结构，结束。否则，不断用父亲的值赋给当前节点，直到合适的位置。时间复杂度O(logN) 在这里插入图片描述

5.出队：首先根节点置空，记录size点（last）的值然后size–，last能放入当前空穴就结束，否则，不断用儿子中最小的值赋给当前节点。时间复杂度O(logN) 在这里插入图片描述 6.队首：直接返回根节点的值，为最小值，O(1)。

二、代码实现头文件：PriorityQueue.h template class PriorityQueue { private: int Capacity = 100; //队列容量 int size; //队列大小 T* data; //队列变量 public: PriorityQueue(); ~PriorityQueue(); int Size(); bool Full(); //判满 bool Empty(); //判空 void Push(T key); //入队 void Pop(); //出队 void Clear(); //清空 T Top(); //队首 }; template PriorityQueue::PriorityQueue() { data = (T*) malloc((Capacity + 1)*sizeof(T)); if (!data) { perror("Allocate dynamic memory"); return; } size = 0; } template PriorityQueue::~PriorityQueue() { while (!Empty()) Pop(); } //判空 template bool PriorityQueue::Empty() { if (size > 0) return false; return true; } //清空 template void PriorityQueue::Clear() { while (!Empty()) Pop(); } //判满 template bool PriorityQueue::Full() { if (size == Capacity) return true; return false; } //大小 template int PriorityQueue::Size() { return size; } //入队 template void PriorityQueue::Push(T key) { // 空则直接入队不能省略 if (Empty()) { data[++size] = key; return; } int i; if (Full()) { perror("Priority queue is full\n"); return; } for (i = ++size; data[i / 2] > key; i /= 2) data[i] = data[i / 2]; data[i] = key; } //出队 template void PriorityQueue::Pop() { int i, child; T min, last; if (Empty()) { perror("Empty queue\n"); return; } min = data[1]; last = data[size--]; for (i = 1; i * 2 if (Empty()) { perror("Priority queue is full\n"); return data[0]; } return data[1]; } 源文件：

银行有1个服务员，n名顾客，每位顾客有到达时间和服务时间。先到的顾客先服务，求总服务时间。输入n 和 n 行输出服务时间

样例输入： 3 1 3 3 5 10 4 样例输出：14

PriorityQueue.cpp

#include"PriorityQueue.h" #include #include using namespace std; const int MAXN = 1000; //事件 struct Event { int arrive; //到达时间 int service; //服务时间 Event(){} Event(int a, int s) { arrive = a; service = s; } }cus[MAXN]; int operator > (const Event& a, const Event& b) { return a.arrive > b.arrive; } int operator Event minCustomer(INT_MIN,0); PriorityQueue request; //顾客 int n, time; while (cin >> n) { for (int i = 0; i Event current = request.Top(); request.Pop(); time = max(current.arrive + current.service, time + current.service); } cout

【本文地址】

二叉树

二叉树

今日新闻

推荐新闻