А Купа це повна структура даних бінарного дерева, яка задовольняє властивість купи: для кожного вузла значення його дочірніх вузлів менше або дорівнює його власному значенню. Купи зазвичай використовуються для реалізації пріоритетних черг, де найменший (або найбільший) елемент завжди знаходиться в корені дерева.

Структура даних купи

Зміст

• Типи куп
• Операції з купою
• Що таке структура даних купи?

  А купа це бінарна структура даних на основі дерева, яка задовольняє властивість купи: значення кожного вузла більше або дорівнює значенню його дочірніх вузлів. Ця властивість гарантує, що кореневий вузол містить максимум або мінімум значення (залежно від типу купи), і значення зменшуються або збільшуються під час руху вниз по дереву.

  java дорівнює

  Типи куп

  Існує два основних типи куп:

  
  
  
  
  • Максимальна купа: Кореневий вузол містить максимальне значення, і значення зменшуються, коли ви рухаєтеся вниз по дереву.
  • Мінімальна купа: Кореневий вузол містить мінімальне значення, і значення збільшуються, коли ви рухаєтеся вниз по дереву.

  Операції з купою

  Загальні операції з купою:

  • Вставка : додає новий елемент до купи, зберігаючи властивість купи.
  • Екстракт Макс/Мін: Вилучає максимальний або мінімальний елемент із купи та повертає його.
  • Heapify : перетворює довільне бінарне дерево на купу.

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

• Heapsort — це алгоритм сортування, який використовує купу для сортування масиву в порядку зростання або спадання.
• Купи використовуються в графових алгоритмах, наприклад Алгоритм Дейкстри і Алгоритм Прима для пошуку найкоротших шляхів і мінімальних охоплюючих дерев.

Бінарна купа

Застосування, переваги та недоліки Heap

Час Складність побудови купи

Порівняння купи та дерева

Чи є структура Heap унікальною під час створення Heap?

Купа Фібоначчі

Ліва Купа

K-ary Heap

Сортування купи

Перевірте, чи дане бінарне дерево є купою

Як перевірити, чи заданий масив представляє бінарну купу?

Ітеративне сортування купи

K’-й найбільший елемент у масиві

K’-й найменший/найбільший елемент у несортованому масиві | Набір 1

Висота повного бінарного дерева (або купи) з N вузлами

Купа Сортування за зменшенням за допомогою мінімальної купи

Надрукуйте всі вузли, менші за значення x, у мінімальній купі.

Дерево турнірів (дерево переможців) і бінарна купа

З'єднайте n мотузок з мінімальними витратами

Максимальна кількість різних елементів після видалення k елементів

K максимальна сума комбінацій з двох масивів

Медіана потоку поточних цілих чисел із використанням STL

Медіана в потоці цілих чисел (постійні цілі числа)

K’-й найбільший елемент у потоці

Найбільший триплетний продукт у потоці

Знайти k чисел із найбільшою кількістю входжень у заданому масиві

Перетворення мінімальної купи в максимальну купу

Перевірте, чи це дерево є мінімальною купою, враховуючи обхід рівня порядку бінарного дерева

Об’єднати k відсортованих масивів | Набір 1

Сортування чисел, що зберігаються на різних машинах

Найменше порушення послідовності

Найбільше порушення послідовності

Максимальна різниця між двома підмножинами з m елементів

Перетворіть BST в Min Heap

Об’єднайте дві бінарні максимальні купи

K-й найбільший суміжний підмасив

Мінімальний добуток k цілих чисел у масиві натуральних чисел

Переставте символи в рядку так, щоб не було двох однакових суміжних символів

Сума всіх елементів між k1-м і k2-м найменшими елементами

Мінімальна сума двох чисел, утворених із цифр масиву

Швидкі посилання:

• Практичні завдання на купі
• Рекомендовано:
  • Вивчіть структуру даних і алгоритми | Підручник DSA