Структура даних Heap та черга пріоритетів у C++

Куча (Heap) — це спеціальна структура даних, основана на дереві, в якому дерево є повним бінарним деревом. Куча не обов'язково є бінарним деревом пошуку (BST).

Вона може бути двох типів:

1. Max-Heap: Значення кожного вузла більше або дорівнює значенням його нащадків. Найбільший елемент знаходиться в корені.
2. Min-Heap: Значення кожного вузла менше або дорівнює значенням його нащадків. Найменший елемент знаходиться в корені.

Кучі зазвичай використовуються для реалізації черг з пріоритетом (Priority Queues), оскільки вони ефективно підтримують операції, такі як вставка та витягування максимального або мінімального елемента.

Основні концепції куч

Повне бінарне дерево: Куча завжди є повним бінарним деревом, що означає, що всі рівні повністю заповнені, за винятком останнього, який заповнюється зліва направо.

Властивість кучі:

Min-Heap: arr[parent] <= arr[child].

Max-Heap: arr[parent] >= arr[child].

Представлення: Кучі зазвичай реалізуються за допомогою масивів для спрощення. Для вузла за індексом i:

Лівий нащадок: 2 * i + 1

Правий нащадок: 2 * i + 2

Батьківський вузол: (i - 1) / 2

Сортування кучею: Використовує кучі для сортування масиву за час O(nlogn):

1. Побудувати max-heap з масиву.
2. Витягнути максимальний елемент і помістити його в кінець масиву.
3. Відновити властивість кучі та повторити для решти елементів.

#include   
using namespace std;  
// Функція для підтримки властивості кучі для піддерева, корінь якого знаходиться в індексі 'i'  
// 'n' — це розмір купи  
void heapify(vector &arr, int n, int i){  
 int largest = i;  
 int left = 2 * i + 1; // Індекс лівого нащадка  
 int right = 2 * 1 + 2; // Індекс правого нащадка  
 // Перевірка, чи існує лівий нащадок і чи більше він поточного найбільшого  
 if(left < n && arr[left] > arr[largest])  
 largest = left;  
 // Перевірка, чи існує правий нащадок і чи більше він поточного найбільшого  
 if(right < n && arr[right] > arr[largest])  
 largest = right;  
 // Якщо найбільший не поточний вузол, міняємо місцями та рекурсивно відновлюємо властивість кучі для піддерева  
 if(largest != i){  
 swap(arr[i], arr[largest]); // Міняємо місцями поточний вузол з найбільшим  
 heapify(arr, n, largest); // Рекурсивно відновлюємо властивість кучі для піддерева  
 }  
}  

// Основна функція для виконання сортування кучею  
void heapSort(vector &arr){  
 int n = arr.size();  
 // Крок 1: Побудувати max-heap з вхідного масиву  
 for(int i = n/2 - 1; i >= 0; i--) // Почати з останнього не-листяного вузла  
 heapify(arr, n, i);  

 // Крок 2: Витягнути елементи з купи один за одним  
 for(int i = n-1; i>0; i--){  
 swap(arr[0], arr[i]); // Переміщаємо корінь (найбільший елемент) в кінець  
 heapify(arr, i, 0); // Відновлюємо властивість кучі для зменшеної купи  
 }  
}  

int main(){  
 vector arr = {10, 5, 20, 2, 15}; // Вхідний масив  
 heapSort(arr); // Виконуємо сортування кучею  
 cout << "Відсортований масив: ";  
 for(int val : arr) cout << val << " ";  
 cout << endl;  
 return 0;  
}

Черга з пріоритетом у C++

Черга з пріоритетом — це абстрактна структура даних, яка дозволяє елементи отримувати на основі їх пріоритету.
У C++ контейнер priority_queue реалізує цю функціональність за допомогою купи (heap).

Черга з пріоритетом Max-Heap (поведінка за замовчуванням)

priority_queue в C++ за замовчуванням працює як max-heap, де найбільший елемент завжди знаходиться на верху.

#include   
#include   
using namespace std;  

int main() {  
 priority_queue maxHeap; // Max-heap  

 maxHeap.push(10);  
 maxHeap.push(5);  
 maxHeap.push(20);  

 cout << "Елементи Max-Heap (від верхнього до нижнього):" << endl;  
 while (!maxHeap.empty()) {  
 cout << maxHeap.top() << " "; // Вивести верхній елемент (найбільший)  
 maxHeap.pop(); // Видалити верхній елемент  
 }  

 return 0;  
}

Черга з пріоритетом Min-Heap

Для реалізації min-heap потрібно вказати greater як компаратор:

#include   
#include   
using namespace std;  

int main() {  
 priority_queue<int, vector<int>, greater<int>> minHeap; // Min-heap  

 minHeap.push(10);  
 minHeap.push(5);  
 minHeap.push(20);  

 cout << "Елементи Min-Heap (від верхнього до нижнього):" << endl;  
 while (!minHeap.empty()) {  
 cout << minHeap.top() << " "; // Вивести верхній елемент (найменший)  
 minHeap.pop(); // Видалити верхній елемент  
 }  

 return 0;  
}

Запитання 1: Kth Largest Element in a Stream

Ви є частиною приймальної комісії університету і повинні відслідковувати k-й найвищий бал з тестів від кандидатів у реальному часі. Це допомагає динамічно визначати прохідні бали для інтерв'ю та прийому, оскільки нові кандидати постійно подають свої бали.

Ваше завдання — реалізувати клас, який для заданого цілого числа k підтримує потік тестових балів і постійно повертає k-й найвищий бал після того, як новий бал буде поданий. Більш конкретно, ми шукаємо k-й найвищий бал у відсортованому списку всіх балів.

Реалізуйте клас KthLargest:

• KthLargest(int k, int[] nums) Ініціалізує об'єкт з цілим числом k та потоком тестових балів nums.
• int add(int val) Додає новий тестовий бал val до потоку і повертає елемент, що представляє k-й найбільший елемент у наборі тестових балів до цього моменту.

Приклад 1:  
Вхід:  
["KthLargest", "add", "add", "add", "add", "add"]  
[[3, [4, 5, 8, 2]], [3], [5], [10], [9], [4]]  
Вихід: [null, 4, 5, 5, 8, 8]  
Пояснення:  
KthLargest kthLargest = new KthLargest(3, [4, 5, 8, 2]);  
kthLargest.add(3); // повертає 4  
kthLargest.add(5); // повертає 5  
kthLargest.add(10); // повертає 5  
kthLargest.add(9); // повертає 8  
kthLargest.add(4); // повертає 8  

Приклад 2:  
Вхід:  
["KthLargest", "add", "add", "add", "add"]  
[[4, [7, 7, 7, 7, 8, 3]], [2], [10], [9], [9]]  
Вихід: [null, 7, 7, 7, 8]  
Пояснення:  
KthLargest kthLargest = new KthLargest(4, [7, 7, 7, 7, 8, 3]);  
kthLargest.add(2); // повертає 7  
kthLargest.add(10); // повертає 7  
kthLargest.add(9); // повертає 7  
kthLargest.add(9); // повертає 8

Підхід

1. Використовувати Min-Heap:

• Найменший елемент у купі є k-им найбільшим елементом, коли розмір купи дорівнює k.
• Додавання/видалення елементів у купі ефективне (O(log k)).

2. Кроки для вирішення:

• Зберігати k та створити min-heap.
• Додати числа з початкового списку nums в купу.
• Обмежити розмір купи до k.
  Видаляти найменші елементи, якщо розмір купи перевищує k.
• Додати нове значення в купу.
• Якщо розмір купи перевищує k, видалити найменший елемент.
• Повернути найменший елемент купи (pq.top() у вашому коді), що є k-им найбільшим елементом.

class KthLargest{  
 int value; // зберігає значення K  
 priority_queue<int, vector<int>, greater<int>> pq; // Min-Heap  
public:  
 KthLargest(int k, vector<int>& nums){  
 value = k;  
 for(int i=0; i < nums.size(); i++){  
 pq.push(nums[i]);  
 if(pq.size() > k) pq.pop(); // Зберігаємо розмір купи рівним k  
 }  
 }  
 int add(int val){  
 pq.push(val); // Додаємо нове значення в купу  
 if(pq.size() > value) pq.pop(); // Зберігаємо розмір купи рівним k  
 return pq.top();  
 }  
}

Запитання 2: Останній камінь вагою

Дано масив цілих чисел stones, де stones[i] — це вага i-го каменя.

Ми граємо в гру з камінням. Кожен хід ми вибираємо два найважчі камені і розбиваємо їх разом. Припустимо, що два найважчі камені мають ваги x та y, де x <= y. Результат цього розбиття:

• Якщо x == y, обидва камені знищуються, і
• Якщо x != y, камінь вагою x знищується, а камінь вагою y набуває нової ваги y - x.

Наприкінці гри залишиться не більше одного каменя.

Поверніть вагу останнього залишкового каменя. Якщо каменів не залишилось, поверніть 0.

Приклад 1:

Вхід: stones = [2,7,4,1,8,1]  
Вихід: 1  
Пояснення:   
Ми об'єднуємо 7 і 8, отримуємо 1, тому масив перетворюється на [2,4,1,1,1], потім,  
ми об'єднуємо 2 і 4, отримуємо 2, тому масив перетворюється на [2,1,1,1], потім,  
ми об'єднуємо 2 і 1, отримуємо 1, тому масив перетворюється на [1,1,1], потім,  
ми об'єднуємо 1 і 1, отримуємо 0, тому масив перетворюється на [1], і це вага останнього каменя.

Приклад 2:

Вхід: stones = [1]  
Вихід: 1

Підхід:

Використовуємо Max-Heap:

1. Створіть max-heap, де найбільше значення завжди знаходиться на верху. Це допомагає нам ефективно витягувати найважчі камені.
2. Поки в купі більше ніж один камінь:

• Витягніть два найбільших камені.
• Якщо їх вага однакова, знищте обидва.
• Якщо їх ваги різні, обчисліть різницю і додайте залишкову вагу назад у купу.

1. Коли цикл завершується, якщо купа порожня, поверніть 0. Якщо залишився тільки один камінь, поверніть його вагу.

class Solution{  
public:  
 int lastStoneWeight(vector<int>& stones){  
 // Крок 1: Створюємо max-heap з каменів  
 priority_queue<int> maxHeap(stones.begin(), stones.end());  
 // Крок 2: Імітуємо процес розбиття  
 while(maxHeap.size() > 1){  
 // Крок 3: Витягуємо два найбільші камені  
 int stone1 = maxHeap.top(); // Найважчий камінь  
 maxHeap.pop(); // Видаляємо його з купи  
 int stone2 = maxHeap.top(); // Другий за важкістю камінь  
 maxHeap.pop(); // Також видаляємо його з купи  
 // Крок 4: Якщо вони не рівні, обчислюємо залишкову вагу  
 if(stone1 != stone2){  
 maxHeap.push(stone1 - stone2); // Додаємо різницю назад у купу  
 }  
 }  
 // Крок 5: Повертаємо вагу останнього каменя або 0, якщо каменів не залишилось  
 return maxHeap.empty() ? 0 : maxHeap.top();  
 }  
}  

// Складність за часом: O(nlogn)  
// Складність за пам'яттю: O(n)

Запитання 3: Kth Largest Element in an Array

Дано масив цілих чисел nums і ціле число k, поверніть k-й найбільший елемент у масиві.

Зверніть увагу, що це k-й найвищий елемент у відсортованому порядку, а не k-й окремий елемент.

Чи можете ви вирішити це без сортування?

Приклад 1:

Вхід: nums = [3,2,1,5,6,4], k = 2  
Вихід: 5

Приклад 2:

Вхід: nums = [3,2,3,1,2,4,5,5,6], k = 4  
Вихід: 4

Підхід:

1. Використовуємо Min-heap для знаходження K-го найбільшого елемента в масиві без повного сортування.
2. Проходимо через всі елементи масиву.
3. Додаємо кожен елемент в Min-Heap.
   4.
   Якщо розмір Min-Heap перевищує "k", видаліть найменший елемент (верхівка Min-Heap).
4. Наприкінці ітерації верхівка Min-Heap містить "k-й" найбільший елемент.

class Solution {  
public:  
 int findKthLargest(vector<int>& nums, int k) {  
 priority_queue<int, vector<int>, greater<int>> pq;  
 for (int num : nums) {  
 pq.push(num);  
 if (pq.size() > k) {  
 pq.pop();  
 }  
 }  
 return pq.top();  
 }  
};  

// Складність за часом: O(nlogk)  
// Складність за пам'яттю: O(k)

Якщо вам сподобалося це пояснення концепцій, будь ласка, підпишіться, поставте лайк і натискайте на дзвіночок

Перекладено з: Heap Data Structure and Priority Queue in C++