what is heap data structure java
Цей посібник пояснює, що таке структура даних Java Heap і пов'язані з нею концепції, такі як Min Heap, Max Heap, Heap Sort, Stack vs Heap з прикладами:
Куча - це спеціальна структура даних у Java. Купа - це структура даних на основі дерева, і її можна класифікувати як повне двійкове дерево. Всі вузли купи розташовані в певному порядку.
=> Завітайте сюди, щоб побачити навчальну серію Java для всіх
Що ви дізнаєтесь:
Структура даних купи в Java
У структурі даних кучі кореневий вузол порівнюється зі своїми нащадками та розміщується відповідно до порядку. Отже, якщо a - це кореневий вузол, а b - його дочірній елемент, то властивість, клавіша (a)> = клавіша (b) генерує максимальну купу.
Вищезазначене відношення між коренем та дочірнім вузлом називається 'Властивість купи'.
Залежно від порядку батьківсько-дочірніх вузлів, купа зазвичай буває двох типів:
# 1) Max-Heap :У Max-Heap ключ кореневого вузла є найбільшим з усіх ключів купи. Слід переконатись, що однакові властивості справедливі для всіх піддерев у купі рекурсивно.
На наведеній нижче схемі показано Зразок максимальної купи. Зверніть увагу, що кореневий вузол більше, ніж його дочірні організації.
# 2) Мін-Купа :У випадку Min-Heap, ключ кореневого вузла є найменшим або мінімальним серед усіх інших ключів, що знаходяться в купі. Як і в Max heap, ця властивість повинна бути рекурсивно істинною у всіх інших піддеревах кучі.
Приклад, дерева Min-heap, показано нижче. Як бачимо, кореневий ключ є найменшим з усіх інших ключів у купі.
Структура даних купи може бути використана в наступних областях:
- Купи переважно використовуються для реалізації пріоритетних черг.
- Особливо min-heap може бути використаний для визначення найкоротших шляхів між вершинами на графіку.
Як уже зазначалося, структура даних купи - це ціле двійкове дерево, яке задовольняє властивості купи для кореня та дочірніх елементів. Ця купа також називається a двійкова купа .
Двійкова купа
Бінарна купа відповідає наведеним нижче властивостям:
- Бінарна купа - це повне бінарне дерево. У повному двійковому дереві всі рівні, крім останнього, заповнені повністю. На останньому рівні клавіші розташовані якомога далі зліва.
- Це задовольняє властивості купи. Двійкова куча може бути max або min-heap, залежно від властивості купи, яку вона задовольняє.
Двійкова купа зазвичай представляється як масив. Оскільки це повне двійкове дерево, його можна легко представити у вигляді масиву. Таким чином, у поданні масиву двійкової купи кореневим елементом буде A (0), де A - масив, що використовується для представлення двійкової купи.
Тож загалом для будь-якого iгоВузол у поданні двійкового масиву масиву, A (i), ми можемо представити індекси інших вузлів, як показано нижче.
| A ((i-1) / 2) | Представляє батьківський вузол |
|---|---|
| Доступ швидший. | Повільніше, ніж стек. |
| A ((2 * i) +1) | Представляє лівий дочірній вузол |
| A ((2 * i) +2) | Представляє правильний дочірній вузол |
Розглянемо таку двійкову купу:
Представлення масиву вищевказаної хв двійкової купи є таким:
Як показано вище, куча обходить відповідно до порядок рівня тобто елементи проходять зліва направо на кожному рівні. Коли елементи на одному рівні вичерпані, ми переходимо на наступний рівень.
Далі ми реалізуємо двійкову купу на Java.
Наведена нижче програма демонструє двійкову купу в Java.
import java.util.*; class BinaryHeap { private static final int d= 2; private int() heap; private int heapSize; //BinaryHeap constructor with default size public BinaryHeap(int capacity){ heapSize = 0; heap = new int( capacity+1); Arrays.fill(heap, -1); } //is heap empty? public boolean isEmpty(){ return heapSize==0; } //is heap full? public boolean isFull(){ return heapSize == heap.length; } //return parent private int parent(int i){ return (i-1)/d; } //return kth child private int kthChild(int i,int k){ return d*i +k; } //insert new element into the heap public void insert(int x){ if(isFull()) throw new NoSuchElementException('Heap is full, No space to insert new element'); heap(heapSize++) = x; heapifyUp(heapSize-1); } //delete an element from the heap at given position public int delete(int x){ if(isEmpty()) throw new NoSuchElementException('Heap is empty, No element to delete'); int key = heap(x); heap(x) = heap(heapSize -1); heapSize--; heapifyDown(x); return key; } //maintain heap property during insertion private void heapifyUp(int i) { int temp = heap(i); while(i>0 && temp > heap(parent(i))){ heap(i) = heap(parent(i)); i = parent(i); } heap(i) = temp; } //maintain heap property during deletion private void heapifyDown(int i){ int child; int temp = heap(i); while(kthChild(i, 1) heap(rightChild)?leftChild:rightChild; } //print the heap public void printHeap() { System.out.print('nHeap = '); for (int i = 0; i Вихід:
nHeap = 7 4 6 1 3 2 5
Мінімальна купа в Java
Мінімальна купа в Java - це повне бінарне дерево. У min-heap кореневий вузол менший за всі інші вузли купи. Загалом, значення ключа кожного внутрішнього вузла менше або дорівнює його дочірнім вузлам.
Що стосується представлення масиву min-heap, якщо вузол зберігається в положенні ‘i’, тоді його лівий дочірній вузол зберігається в положенні 2i + 1, а потім правий дочірній вузол знаходиться в положенні 2i + 2. Позиція (i-1) / 2 повертає батьківський вузол.
Нижче наведено різні операції, що підтримуються min-heap.
# 1) Вставити (): Спочатку в кінці дерева додається новий ключ. Якщо ключ більший за батьківський вузол, властивість купи зберігається. В іншому випадку нам потрібно прокрутити ключ вгору, щоб виконати властивість купи. Операція вставки в хвилину купи займає час O (log n).
# 2) extractMin (): Ця операція видаляє мінімальний елемент із купи. Зверніть увагу, що властивість heap слід підтримувати після видалення кореневого елемента (min-елемента) з купи. Вся ця операція приймає O (Logn).
# 3) getMin (): getMin () повертає корінь купи, який також є мінімальним елементом. Ця операція виконується за час O (1).
Нижче наведено приклад дерева для Min-heap.
На наведеній вище схемі показано дерево міні-купи. Ми бачимо, що корінь дерева - це мінімальний елемент у дереві. Оскільки корінь знаходиться в розташуванні 0, його ліва дитина розміщується на рівні 2 * 0 + 1 = 1, а права дитина знаходиться на рівні 2 * 0 + 2 = 2.
Мінімальний алгоритм купи
Нижче наведено алгоритм побудови міні-купи.
procedure build_minheap Array Arr: of size N => array of elements { repeat for (i = N/2 ; i >= 1 ; i--) call procedure min_heapify (A, i); } procedure min_heapify (var A( ) , var i, var N) { var left = 2*i; var right = 2*i+1; var smallest; if(left <= N and A(left) < A( i ) ) smallest = left; else smallest = i; if(right <= N and A(right) < A(smallest) ) smallest = right; if(smallest != i) { swap A( i ) and A( smallest )); call min_heapify (A, smallest,N); } }Реалізація міні-купи в Java
Ми можемо реалізувати min-heap або за допомогою масиву, або черг пріоритетів. Реалізація min-heap за допомогою пріоритетних черг є реалізацією за замовчуванням, оскільки пріоритетна черга реалізована як min-heap.
Наступна програма Java реалізує min-heap за допомогою масивів. Тут ми використовуємо представлення масиву для купи, а потім застосовуємо функцію heapify для підтримки властивості купи кожного елемента, доданого до купи. Нарешті, ми відображаємо купу.
class Min_Heap { private int() HeapArray; private int size; private int maxsize; private static final int FRONT = 1; //constructor to initialize the HeapArray public Min_Heap(int maxsize) { this.maxsize = maxsize; this.size = 0; HeapArray = new int(this.maxsize + 1); HeapArray(0) = Integer.MIN_VALUE; } // returns parent position for the node private int parent(int pos) { return pos / 2; } // returns the position of left child private int leftChild(int pos) { return (2 * pos); } // returns the position of right child private int rightChild(int pos) { return (2 * pos) + 1; } // checks if the node is a leaf node private boolean isLeaf(int pos) { if (pos >= (size / 2) && pos HeapArray(leftChild(pos)) || HeapArray(pos) > HeapArray(rightChild(pos))) { // swap with left child and then heapify the left child if (HeapArray(leftChild(pos)) = maxsize) { return; } HeapArray(++size) = element; int current = size; while (HeapArray(current) = 1; pos--) { minHeapify(pos); } } // remove and return the heap elment public int remove() { int popped = HeapArray(FRONT); HeapArray(FRONT) = HeapArray(size--); minHeapify(FRONT); return popped; } } class Main{ public static void main(String() arg) { //construct a min heap from given data System.out.println('The Min Heap is '); Min_Heap minHeap = new Min_Heap(7); minHeap.insert(12); minHeap.insert(15); minHeap.insert(30); minHeap.insert(40); minHeap.insert(50); minHeap.insert(90); minHeap.insert(45); minHeap.minHeap(); //display the min heap contents minHeap.display(); //display root node of the min heap System.out.println('The Min val(root node):' + minHeap.remove()); } } Вихід:
Максимальна купа в Java
Максимальна купа - це також повне двійкове дерево. У максимальній купі кореневий вузол більше або дорівнює дочірнім вузлам. Загалом, значення будь-якого внутрішнього вузла в максимальній купі більше або дорівнює його дочірнім вузлам.
Поки максимальна купа відображається на масив, якщо який-небудь вузол зберігається в положенні ‘i’, то його ліва дочірня частина зберігається на 2i +1, а права дочірня на 2i + 2.
Типовий Max-heap буде виглядати, як показано нижче:
На наведеній вище схемі ми бачимо, що кореневий вузол є найбільшим у кучі, а його дочірні вузли мають значення, менші за кореневий вузол.
Подібно до min-heap, максимальна купа також може бути представлена як масив.
Отже, якщо A - це масив, що представляє максимальну купу, тоді A (0) є кореневим вузлом. Подібним чином, якщо A (i) - це будь-який вузол у максимальній купі, то нижче наведено інші сусідні вузли, які можна представити за допомогою масиву.
- A ((i-1) / 2) представляє батьківський вузол A (i).
- A ((2i +1)) представляє лівий дочірній вузол A (i).
- A (2i + 2) повертає правий дочірній вузол A (i).
Операції, які можна виконувати на Max Heap, наведені нижче.
# 1) Вставка: Операція 'Вставлення' вставляє нове значення в дерево максимального купи. Він вставляється в кінець дерева. Якщо новий ключ (значення) менший за батьківський вузол, властивість купи зберігається. В іншому випадку дерево потрібно звалити, щоб зберегти властивість купи.
яка найкраща безкоштовна програма для чищення комп’ютерів?
Складність у часі операції вставки становить O (log n).
# 2) ExtractMax: Операція ExtractMax видаляє максимальний елемент (корінь) з максимальної купи. Операція також нагромаджує максимальну купу, щоб зберегти властивість купи. Складність часу цієї операції становить O (log n).
# 3) getMax: Операція getMax повертає кореневий вузол максимальної купи з часовою складністю O (1).
Наведена нижче програма Java реалізує максимальну купу. Тут ми використовуємо ArrayList для представлення максимальних елементів купи.
import java.util.ArrayList; class Heap { void heapify(ArrayList hT, int i) { int size = hT.size(); int largest = i; int l = 2 * i + 1; int r = 2 * i + 2; if (l hT.get(largest)) largest = l; if (r hT.get(largest)) largest = r; if (largest != i) { int temp = hT.get(largest); hT.set(largest, hT.get(i)); hT.set(i, temp); heapify(hT, largest); } } void insert(ArrayList hT, int newNum) { int size = hT.size(); if (size == 0) { hT.add(newNum); } else { hT.add(newNum); for (int i = size / 2 - 1; i >= 0; i--) { heapify(hT, i); } } } void deleteNode(ArrayList hT, int num) { int size = hT.size(); int i; for (i = 0; i = 0; j--) { heapify(hT, j); } } void printArray(ArrayList array, int size) { for (Integer i : array) { System.out.print(i + ' '); } System.out.println(); } } class Main{ public static void main(String args()) { ArrayList array = new ArrayList(); int size = array.size(); Heap h = new Heap(); h.insert(array, 3); h.insert(array, 4); h.insert(array, 9); h.insert(array, 5); h.insert(array, 2); System.out.println('Max-Heap array: '); h.printArray(array, size); h.deleteNode(array, 4); System.out.println('After deleting an element: '); h.printArray(array, size); } } Вихід:
Черга пріоритетів у купі Java
Структура даних черги пріоритетів у Java може бути безпосередньо використана для представлення міні-купи. За замовчуванням у черзі пріоритетів реалізовано min-heap.
Наведена нижче програма демонструє міні-купу в Java за допомогою черги пріоритетів.
import java.util.*; class Main { public static void main(String args()) { // Create priority queue object PriorityQueue pQueue_heap = new PriorityQueue(); // Add elements to the pQueue_heap using add() pQueue_heap.add(100); pQueue_heap.add(30); pQueue_heap.add(20); pQueue_heap.add(40); // Print the head (root node of min heap) using peek method System.out.println('Head (root node of min heap):' + pQueue_heap.peek()); // Print min heap represented using PriorityQueue System.out.println('
Min heap as a PriorityQueue:'); Iterator iter = pQueue_heap.iterator(); while (iter.hasNext()) System.out.print(iter.next() + ' '); // remove head (root of min heap) using poll method pQueue_heap.poll(); System.out.println('
Min heap after removing root node:'); //print the min heap again Iterator iter2 = pQueue_heap.iterator(); while (iter2.hasNext()) System.out.print(iter2.next() + ' '); } } Вихід:
Максимальна купа черги пріоритетів у Java
Щоб представити максимальну купу в Java за допомогою черги пріоритетів, нам потрібно скористатися Collections.reverseOrder, щоб повернути назад мінімальну купу. Черга пріоритетів безпосередньо представляє міні-купу в Java.
Ми застосували Max Heap за допомогою черги пріоритетів у наведеній нижче програмі.
import java.util.*; class Main { public static void main(String args()) { // Create empty priority queue //with Collections.reverseOrder to represent max heap PriorityQueue pQueue_heap = new PriorityQueue(Collections.reverseOrder()); // Add items to the pQueue using add() pQueue_heap.add(10); pQueue_heap.add(90); pQueue_heap.add(20); pQueue_heap.add(40); // Printing all elements of max heap System.out.println('The max heap represented as PriorityQueue:'); Iterator iter = pQueue_heap.iterator(); while (iter.hasNext()) System.out.print(iter.next() + ' '); // Print the highest priority element (root of max heap) System.out.println('
Head value (root node of max heap):' + pQueue_heap.peek()); // remove head (root node of max heap) with poll method pQueue_heap.poll(); //print the max heap again System.out.println('
Max heap after removing root: '); Iterator iter2 = pQueue_heap.iterator(); while (iter2.hasNext()) System.out.print(iter2.next() + ' '); } } Вихід:
Сортування купи на Java
Сортування купи - це техніка сортування порівняння, подібна до сортування виділення, коли ми вибираємо максимум елемента в масиві для кожної ітерації. Сортування купи використовує структуру даних Heap і сортує елементи, створюючи мінімальну або максимальну купу з елементів масиву, що підлягають сортуванню.
Ми вже обговорювали, що в купі min та max кореневий вузол містить мінімальний та максимальний елементи масиву відповідно. При сортуванні купи кореневий елемент купи (min або max) видаляється та переміщується до відсортованого масиву. Потім залишок купи скупчується для збереження властивості купи.
Отже, ми повинні виконати два кроки рекурсивно, щоб сортувати даний масив за допомогою купі сортування.
- Побудуйте купу з даного масиву.
- Неодноразово видаляйте кореневий елемент із купи та переміщуйте його до відсортованого масиву. Засипте залишок купи.
Складність часу сортування купи у всіх випадках становить O (n log n). Космічна складність - O (1).
Алгоритм сортування купи на Java
Нижче наведено алгоритми сортування купи для сортування даного масиву у порядку зростання та зменшення.
# 1) Алгоритм сортування по купі для сортування за зростанням:
- Створіть максимальну купу для даного масиву для сортування.
- Видаліть корінь (максимальне значення у вхідному масиві) і перемістіть його до відсортованого масиву. Розмістіть останній елемент у масиві в корені.
- Унеможливити новий корінь купи.
- Повторюйте кроки 1 і 2, поки весь масив не буде відсортовано.
# 2) Алгоритм сортування кучі для сортування за спаданням:
- Побудуйте min купу для даного масиву.
- Видаліть корінь (мінімальне значення в масиві) і поміняйте його місцями з останнім елементом масиву.
- Унеможливити новий корінь купи.
- Повторюйте кроки 1 і 2, поки весь масив не буде відсортовано.
Реалізація купі сорту в Java
Наведена нижче програма Java використовує сортування купи, щоб сортувати масив за зростанням. Для цього ми спочатку створюємо максимальну купу, а потім рекурсивно поміняємо місцями і згрупуємо кореневий елемент, як зазначено в наведеному вище алгоритмі.
import java.util.*; class HeapSort{ public void heap_sort(int heap_Array()) { int heap_len = heap_Array.length; // construct max heap for (int i = heap_len / 2 - 1; i >= 0; i--) { heapify(heap_Array, heap_len, i); } // Heap sort for (int i = heap_len - 1; i >= 0; i--) { int temp = heap_Array(0); heap_Array(0) = heap_Array(i); heap_Array(i) = temp; // Heapify root element heapify(heap_Array, i, 0); } } void heapify(int heap_Array(), int n, int i) { // find largest value int largest = i; int left = 2 * i + 1; int right = 2 * i + 2; if (left heap_Array(largest)) largest = left; if (right heap_Array(largest)) largest = right; // recursively heapify and swap if root is not the largest if (largest != i) { int swap = heap_Array(i); heap_Array(i) = heap_Array(largest); heap_Array(largest) = swap; heapify(heap_Array, n, largest); } } } class Main{ public static void main(String args()) { //define input array and print it int heap_Array() = {6,2,9,4,10,15,1,13}; System.out.println('Input Array:' + Arrays.toString(heap_Array)); //call HeapSort method for given array HeapSort hs = new HeapSort(); hs.heap_sort(heap_Array); //print the sorted array System.out.println('Sorted Array:' + Arrays.toString(heap_Array)); } } Вихід:
Загальна часова складність техніки сортування купи становить O (nlogn). Складність у часі техніки купірування становить O (logn). Тоді як складність часу побудови купи становить O (n).
Стек проти купи в Java
Давайте тепер розкладемо деякі розбіжності між структурою даних стека та купою.
Стек Купи Стек - це лінійна структура даних. Купа - це ієрархічна структура даних. Дотримується впорядкування LIFO (Last In, First Out). Обхід в порядку порядку. В основному використовується для статичного розподілу пам'яті. Використовується для динамічного розподілу пам'яті. Пам'ять виділяється суміжно. Пам'ять розподіляється у випадкових місцях. Розмір стека обмежений відповідно до операційної системи. Операційна система не обмежує розмір купи. Стек має доступ лише до локальних змінних. До купи присвоєні глобальні змінні. Виділення / вивільнення пам'яті відбувається автоматично. Розподіл / вивільнення повинен виконуватися програмістом вручну. Стек може бути реалізований за допомогою Arrays, Linked List, ArrayList тощо або будь-яких інших лінійних структур даних. Купа реалізована за допомогою масивів або дерев. Вартість обслуговування, якщо менше. Дорожче в обслуговуванні. Це може призвести до дефіциту пам'яті, оскільки пам'ять обмежена. Не вистачає пам'яті, але може постраждати від фрагментації пам'яті.
Часті запитання
Q # 1) Стек швидший за Heap?
Відповідь: Стек швидший, ніж купа, оскільки доступ є стеком лінійним порівняно з купою.
Q # 2) Для чого використовується купа?
Відповідь: Купа в основному використовується в алгоритмах, які знаходять мінімальний або найкоротший шлях між двома точками, як алгоритм Дейкстри, для сортування за допомогою сортування купи, для реалізації черги пріоритетів (min-heap) тощо.
Q # 3) Що таке купа? Які її типи?
Відповідь: Купа - це ієрархічна структура даних на основі дерева. Купа - це повне двійкове дерево. Купи бувають двох типів, тобто Максимальна купа, в якій кореневий вузол є найбільшим серед усіх вузлів; Мінімальна купа, в якій кореневий вузол є найменшим або мінімальним серед усіх ключів.
Q # 4) Які переваги Heap перед стеком?
Відповідь: Основна перевага купи над стеком - це купа, пам'ять динамічно розподіляється, і тому немає обмежень щодо кількості пам'яті, яку можна використовувати. По-друге, у стеку можуть бути виділені лише локальні змінні, тоді як ми також можемо виділити глобальні змінні в купі.
Q # 5) Чи може Heap мати дублікати?
Відповідь: Так, немає обмежень на наявність у купі вузлів із повторюваними ключами, оскільки купа є повним бінарним деревом, і воно не задовольняє властивостям бінарного дерева пошуку.
Висновок
У цьому підручнику ми обговорили типи купи та сортування купи за допомогою типів купи. Ми також бачили детальну реалізацію її типів на Java.
=> Ознайомтесь з Ідеальним посібником з навчання Java тут.
Рекомендована література
- Підручник з графіків Java - Як реалізувати структуру даних графіків
- Вступ до структур даних на C ++
- Сортування купи в C ++ із прикладами
- Структура даних дерева та купи AVL у C ++
- Структура даних двійкового дерева в C ++
- Структура даних черги в C ++ з ілюстрацією
- Структура даних кругового зв’язаного списку на C ++ з ілюстрацією
- Основи Java: Синтаксис Java, клас Java та основні концепції Java
