Реализация очереди с приоритетами с помощью частично упорядоченных деревьев. Операция удаления элемента из очереди. - EcsFlash/DataTypes GitHub Wiki

Частично упорядоченное дерево

Скажем что ЧУД - бинарное дерево, которое в нашем случае строится по правилу: приоритет любого элемента больше чем приоритет его потомков. Также стоит сказать что частично упорядоченное дерево является сбалансированным деревом, то есть высота его поддеревьев отличается не больше чем на еденицу. image ПОДРОБНЕЕ ПРО ЭТУ ЗАЛУПУ НАПИСАНО В ПИРАМИДАЛЬНЫХ СОРТИ-что-то там тык

Вставка элемента

Вставка элемента происходит следующим образом:

  1. На самом последнем/предпоследнем ярусе дерева находим первый слева элемент, имеющий либо одного либо ноль потомков.

image

  1. Затем к этому элементу добавляем потомка, причем заполнение уже получается последнего яруса идет слева на право. То есть если у найденного на первом шаге элемента есть один потомок, то он гарантированно левый, и значит добавляем правого. Если у элемента нет потомков, добавляем левого.

image

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

Всё, вставка завершена.

Удаление элемента

Удаление элемента также происходит в три шага:

  1. Находим на последнем ярусе самый правый элемент
  2. Меняем его местами с корнем и удаляем(тот, что на нижнем ярусе)
  3. Просеиваем новоиспеченный корень вниз image

Код

#pragma once
#include "queue"
#include "stack"
#include <iostream>
using namespace std;
template <typename T>
class PHQueue {
	struct node {
		T data;
		int PRIORA;
		node* left;
		node* right;
		node(T _data, int p) {
			data = _data;
			PRIORA = p;
			left = right = nullptr;
		}
		friend ostream& operator<<(ostream& os, node*& node) {
			os << '(' << node->data << ',' << node->PRIORA << ')';
			return os;
		}
	};
	node* root;
	int size;

	void balance(node*& node) {
		if (node) {
			if (node->left && node->left->PRIORA > node->PRIORA) {
				swap(node, node->left);
			}
			if (node->right && node->right->PRIORA > node->PRIORA) {
				swap(node, node->right);
			}
			balance(node->left);

			balance(node->right);

		}
	}
	node* balanceNewbie(node* n, node* newbie) {
		if (n) {
			if (n == newbie) {
				return n;
			}
			node* left = balanceNewbie(n->left, newbie);
			node* right = balanceNewbie(n->right, newbie);
			if (left) {
				if (left->PRIORA > n->PRIORA) {
					swap(left, n);
				}
			}
			else if (right) {
				if (right->PRIORA > n->PRIORA) {
					swap(right, n);
				}
			}

		}
		else {
			return nullptr;
		}
	}

	void swap(node*& node1, node*& node2) {
		T tempD = node1->data;
		int tempP = node1->PRIORA;
		node1->data = node2->data;
		node1->PRIORA = node2->PRIORA;
		node2->data = tempD;
		node2->PRIORA = tempP;
	}
public:
	PHQueue() {
		root = nullptr;
		size = 0;
	}
	void add(T data, int p) {
		if (root) {
			// создаем очередб для обхода в ширину
			queue<node*> q;
			//  добавляем корень в очередь
			q.push(root);
			// инициализируем огрызка(0 или 1 наследник)
			node* temp = root;
			// пока очередь не пуста продолжаем обход
			while (!q.empty()) {
				// достаем из очереди предполагаемого огрызка
				temp = q.front();
				// если есть оба наслдника - удаляем(если не огрызок),
				// таким образом огрызок останется в начале очереди
				if (temp->left && temp->right) {
					q.pop();
				}
				// как только обнаружили огрызка, прекращаем обход
				else {
					break;
				}
				// если все наследники на месте, продолжаем
				if (temp->left) {
					q.push(temp->left);
				}
				if (temp->right) {
					q.push(temp->right);
				}
			}
			if (temp->left) {
				temp->right = new node(data, p);
				balanceNewbie(root, temp->right);
			}
			else {
				temp->left = new node(data, p);
				balanceNewbie(root, temp->left);
			}
		}
		else {
			root = new node(data, p);
		}
	}
	T pop2() {
		if (root) {
			queue<node*> q;
			T result = root->data;
			q.push(root);
			int _size = 0;
			node* temp = root;
			node* parent = nullptr;
			while (!q.empty()) {
				temp = q.front();
				q.pop();
				if (temp->left) {
					parent = temp;
					q.push(temp->left);
				}
				if (temp->right) {
					parent = temp;
					q.push(temp->right);
				}
			}
			if (parent) {
				if (parent->left == temp) {
					parent->left = nullptr;
				}
				else if (parent->right == temp) {
					parent->right = nullptr;
				}
			}
			else {
				root = nullptr;
			}
			root->data = temp->data;
			root->PRIORA = temp->PRIORA;
			delete temp;
			balance(root);
			return result;
		}
	}
	void print() {
		if (root) {
			queue<node*> q;
			q.push(root);
			node* temp = root;
			while (!q.empty()) {
				temp = q.front();
				cout << temp << '\t';
				q.pop();
				if (temp->left) {
					q.push(temp->left);
				}if (temp->right) {
					q.push(temp->right);
				}
			}

		}
		cout << endl;
	}
	T peek() {
		if (root) {
			return root->data;
		}
		throw invalid_argument("error");
	}
	bool isEmpty() {
		return root == nullptr;
	}
};

Разбор нюансов и функций

Функция swap меняет местами данные в узлах дерева.

Функция balanceNewbie пропихивает новоиспеченный элемент на его законное место в дереве, согласно приоритету. И вот тут есть нюанс - для того чтобы поставить элемент на его позицию, требуется знать полный путь от корня до новичка, чтобы последовательно сравнивать и менять местами элементы по необходимости. Для поиска полного пути воспользуется рекурсией, а точнее её фишкой - стеком вызовов. По сути мы выполняем обход в глубину, с одной особенностью - все ветки рекурсии не достигнувшие искомого элемента просто "умирают", а в ветке с необходимым элементом мы производим обмен данными у узлов при необходимости.

Функция balance просеивает новый корень после удаления элемента вниз.

обля

⚠️ **GitHub.com Fallback** ⚠️