Реализация очереди с приоритетами с помощью массива, линейного списка и бинарного дерева поиска. Сравнение реализаций. - EcsFlash/DataTypes GitHub Wiki

Из прошлого пункта мы узнали что очередь с приоритетом необходима для того чтобы доставать из нее самый приоритетный элемент, при этом кладя в нее элементы в любом порядке.

При помощи массива.

Все объекты хранятся в массиве/векторе, операция вставки вставляет элемент на место, согласно приоритету и при необходимости сдвигает все последующие. Если вдруг нам не хватает места, можно либо выкинуть ошибку, либо расширить массив. Я буду кидаться ошибками. При удалении элемента будем двигать все элементы влево. На самом деле можно было бы сделать что-то типо кольцевой очереди, но мне лень, возможно позже она появится.

Наивная реализация на массиве

#pragma once
#include <string>
#include <stdexcept>
using namespace std;



class PArrQueue {
	
	struct Elem {
		int priority;
		string value;
	};
	Elem* ptr;
	Elem** arr;
	int cap;
	int len;
public:
	PArrQueue(int n) {
		cap = n;
		arr = new Elem*[cap];
		for (int i = 0; i < cap; i++) {
			arr[i] = nullptr;
		}
		len = 0;
		ptr = *arr;
	}

	void Push(int p, string v) {
		Elem* e = new Elem{ p,v };
		if (len >= cap) {
			throw "no mama";
		}
		else {
			int i = 0;
			while(arr[i])
			{
				if (arr[i] && arr[i]->priority < e->priority) {
					for (int j = len; j > i; j--) {
						swap(arr[j], arr[j - 1]);
					}
					arr[i] = e;
					len++;
					return;
				}
				i++;
			}
			arr[i] = e;
			len++;
			return;
		}
		
	}

	string Pop() {
		if (!arr[0]) {
			throw "no data";
		}
		string result = (*arr[0]).value;
		arr[0] = nullptr;
		for (int i = 0; i < len; i++) {
			swap(arr[i], arr[i + 1]);
		}
		return result;
	}

	bool isEmpty() {
		return arr[0] == nullptr;
	}

	void clear() {
		for (int i = 0; i < cap; i++) {
			arr[i] = nullptr;
		}
		len = 0;
	}
};

При помощи списка

В данном случае всё гораздо проще. Список получается "самоогранизующимся". То есть при добавлении элемента в очередь он сразу встает на своё место согласно приоритету, а pop() просто удаляет первый элемент.

Реализация

#pragma once


#pragma once
#include <iostream>
#include <sstream>
using namespace std;



class PListQueue {
	struct Elem {
		int priority;
		string value;
	};
	struct Node {
		Elem data;
		Node* next;
		Node(int p, string v) {
			this->data = Elem{ p,v };
			next = nullptr;
		}
	};
	Node* head;
	void print(Node* node) {
		if (node) {
			cout << node->data.value << " ";
			print(node->next);
		}
	}
	void deleteAfter(Node* whereTo) {
		if (whereTo) {
			Node* temp = whereTo->next;
			if (temp) {
				whereTo->next = whereTo->next->next;
				delete temp;
			}
		}
	}
	void addAfter(Node* whereTo, int p, string v) {
		if (whereTo) {
			Node* newElement = new Node(p, v);
			newElement->next = whereTo->next;
			whereTo->next = newElement;
		}
	}
	void addToHead(int p, string v) {
		Node* newHead = new Node(p, v);
		newHead->next = head;
		head = newHead;
	}
	void deleteFirst() {
		if (!isEmpty()) {
			Node* temp = head->next;
			delete head;
			head = temp;
		}
	}
public:
	PListQueue() {
		head = nullptr;
	}
	~PListQueue() {
		clear();
	}
	

	void Push(int p, string v) {
		
		if (!isEmpty()) {
			if (p > head->data.priority) {
				addToHead(p, v);
			}
			else {
				Node* temp = head;
				while (temp->next && temp->next->data.priority > p) {
					temp = temp->next;
				};
				addAfter(temp, p, v);
			}
			
		}
		else {
			addToHead(p, v);
		}
	}

	string Pop() {
		if (!isEmpty()) {
			string result = head->data.value;
			deleteFirst();
		}
		else {
			throw "no mama";
		}
	}
	void clear() {
		while (!isEmpty())
		{
			deleteFirst();
		}
	}
	bool isEmpty() {
		return head == nullptr;
	}
	
	
	void print()
	{
		print(head);
	}

	void println()
	{
		Node* temp = head;
		while (temp)
		{
			cout << temp->data.value << " ";
			temp = temp->next;
		}
	}

	
};

На бинарном дереве поиска

Тут все тоже довольно тривиально. По правилам построения бинарного дерева поиска сразу понятно что элемент с наибольшим приоритетом будет в конце правой ветви(или корнем), а элемент с меньшим приоритетом - в конце левой ветви(тоже может быть корнем). Процедура вставки ничем не отличается от обычной вставки в бинарное дерево,только сравнивать мы будем не значения в узлах, а приоритеты. Удалять мы будем конечный элемент из правой ветви.

Реализция

#pragma once
#include <string>
#include <iostream>
using namespace std;

class PTreeQueue {
	struct Elem {
		int priority;
		string value;
	};
	struct Node {
		Elem data;
		Node* left;
		Node* right;
		Node(int p, string v) {
			data = Elem{ p,v };
			left = right = nullptr;
		}
	};
	Node* root;

	void insert(Node*& node, int p, string v) {
		if (!node) {
			node = new Node(p, v);
		}
		else {
			if (p >= node->data.priority) {
				insert(node->right, p, v);
			}
			else {
				insert(node->left, p, v);
			}
		}
	}

	

	Node*& toDelete(Node*& temp) {
		
		if (temp->right) {
			return toDelete(temp->right);
		}
		else {
			return temp;
		}
	}
	void clear(Node*& node) {
		if (node) {
			clear(node->right);
			clear(node->left);
			delete node;
			node = nullptr;
		}
	}
public:
	PTreeQueue() {
		root = nullptr;
	}
	~PTreeQueue() {
		clear();
	}
	bool isEmpty() {
		return root == nullptr;
	}
	void Push(int p, string v) {
		insert(root, p,v);
	}
	
	void clear() {
		clear(root);
	}
	string Pop() {
		if (!isEmpty()) {
			string result;
			Node*& node = toDelete(root);
			result = node->data.value;
			Node* temp = node;
			node = node->left;
			delete temp;
			temp = nullptr;
			return result;
		}
		else {
			throw "no mama";
		}
	}
};

Сравнение реализаций

Вставка:

на массиве - O(n), даже если умудриться искать место для элемента бинарным поиском - дальнейший сдвиг всех соседей будет всё равно линейным.
на списке - в данном случае O(n), но есть подозрение что можно извернуться и присобачить бинарный поиск для определения места для элемента.
на дереве поиска - O(log(n)) в среднем и O(n) в худшем случае.

Удаление:

на массиве - в данном случае O(n)
на списке - O(1)
на дереве - O(log(n)) в среднем, O(n) в худшем. Но можно извернуться, отдельно храня в классе указатель на "самый правый" элемент и сделать удаление O(1)

обля

⚠️ GitHub.com Fallback ⚠️