what is heap data structure java
Този урок обяснява какво е Java Heap Data Structure и свързани понятия като Min Heap, Max Heap, Heap Sort, Stack vs Heap с примери:
Купчината е специална структура от данни в Java. Купата е дървовидна структура от данни и може да бъде класифицирана като цялостно двоично дърво. Всички възли на купчината са подредени в определен ред.
=> Посетете тук, за да видите серията за обучение за Java за всички
Какво ще научите:
- Структура на данните от купчина в Java
- Стек срещу купчина в Java
- Заключение
Структура на данните от купчина в Java
В структурата на данните за купчината коренният възел се сравнява със своите деца и се подрежда според реда. Така че, ако a е корен възел и b е негово дъщерно устройство, тогава свойството, ключ (a)> = ключ (b) ще генерира максимална купчина.
Горната връзка между корена и дъщерния възел се нарича „Свойство на купчината“.
В зависимост от реда на възлите родител-дете, купчината обикновено е два вида:
# 1) Max-Heap :В Max-Heap ключът на коренния възел е най-големият от всички ключове в купчината. Трябва да се гарантира, че едно и също свойство е вярно за всички поддървета в купчината рекурсивно.
Диаграмата по-долу показва примерна максимална купчина. Имайте предвид, че коренният възел е по-голям от своите деца.
# 2) Мин купчина :В случай на Min-Heap ключът на кореновия възел е най-малкият или минимум от всички останали ключове в купчината. Както при Max heap, това свойство трябва да бъде рекурсивно вярно във всички останали поддървета в купчината.
Пример, на дърво с минимална купчина, е показано по-долу. Както виждаме, главният ключ е най-малкият от всички останали ключове в купчината.
Структура от данни за купчина може да се използва в следните области:
- Купчините се използват най-вече за изпълнение на приоритетни опашки.
- Особено min-heap може да се използва за определяне на най-кратките пътеки между върховете в графика.
Както вече споменахме, структурата на данните от купчината е цялостно двоично дърво, което удовлетворява свойството на купчината за root и потомците. Тази купчина се нарича също като двоична купчина .
Двоична купчина
Двоична купчина отговаря на следните свойства:
- Двоична купчина е пълно двоично дърво. В пълно двоично дърво всички нива с изключение на последното ниво са напълно запълнени. На последното ниво бутоните са възможно най-вляво.
- Той отговаря на свойството на купчината. Двоичната купчина може да бъде 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 (): Тази операция премахва минималния елемент от купчината. Обърнете внимание, че свойството на купчината трябва да се поддържа след премахване на основния елемент (минимален елемент) от купчината. Цялата тази операция отнема O (Logn).
# 3) getMin (): getMin () връща корена на купчината, който е и минималният елемент. Тази операция се извършва за O (1) време.
Дадено по-долу е примерно дърво за Min-heap.
Горната диаграма показва дърво с минимална купчина. Виждаме, че коренът на дървото е минималният елемент в дървото. Тъй като коренът е на място 0, лявото му дете е поставено на 2 * 0 + 1 = 1, а дясното дете е на 2 * 0 + 2 = 2.
Алгоритъм за минимална купчина
По-долу е даден алгоритъмът за изграждане на min-heap.
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 с помощта на масиви. Тук използваме представяне на масив за heap и след това прилагаме функцията heapify, за да поддържаме свойството heap на всеки елемент, добавен към купчината. Накрая показваме купчината.
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, max heap може също да бъде представен като масив.
Така че, ако A е масив, който представлява Max heap, тогава 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. По подразбиране приоритетната опашка изпълнява 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, за да обърнем минималната купчина. Приоритетната опашка директно представлява min-heap в 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
Сортирането на купчина е техника за сортиране на сравнение, подобно на сортирането на селекция, при което избираме максимален елемент в масива за всяка итерация. Сортирането на купчина използва структурата на данните на купчината и сортира елементите, като създава минимална или максимална купчина от елементите на масива, които ще бъдат сортирани.
Вече обсъдихме, че в купчината min и max коренният възел съдържа съответно минималния и максималния елемент на масива. При сортиране на купчината основният елемент на купчината (мин. Или макс.) Се премахва и премества в сортирания масив. След това останалата купчина се натрупва, за да се поддържа свойството на купчината.
Така че трябва да изпълним две стъпки рекурсивно, за да сортираме дадения масив, използвайки сортиране на купчини.
- Изградете купчина от дадения масив.
- Многократно премахвайте основния елемент от купчината и го премествайте в сортирания масив. Утежнете останалата купчина.
Сложността във времето на сортирането на купчина е O (n log n) във всички случаи. Космическата сложност е O (1).
Алгоритъм за сортиране на купчини в Java
По-долу са дадени алгоритмите за сортиране на купчини за сортиране на дадения масив във възходящ и низходящ ред.
# 1) Алгоритъм за сортиране на купчини за сортиране във възходящ ред:
- Създайте максимална купчина за даден масив, който да бъде сортиран.
- Изтрийте корена (максималната стойност във входния масив) и го преместете в сортирания масив. Поставете последния елемент в масива в корена.
- Увеличете новия корен на купчината.
- Повторете стъпки 1 и 2, докато целият масив не бъде сортиран.
# 2) Алгоритъм за сортиране на купчини за сортиране в низходящ ред:
- Изградете мин. Купчина за дадения масив.
- Премахнете корена (минимална стойност в масива) и го заменете с последния елемент в масива.
- Увеличете новия корен на купчината.
- Повторете стъпки 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). Обхождането е в порядък на ниво. Използва се предимно за статично разпределение на паметта. Използва се за динамично разпределение на паметта. Паметта се разпределя непрекъснато. Паметта се разпределя на произволни места. Размерът на стека е ограничен в зависимост от операционната система. Няма ограничение за размера на купчината, налагано от операционната система. Стекът има достъп само до локални променливи. Heap има разпределени глобални променливи. Разпределението / освобождаването на паметта е автоматично. Разпределението / освобождаването трябва да се извърши ръчно от програмиста. Стекът може да бъде реализиран с помощта на масиви, свързан списък, ArrayList и др. Или всякакви други линейни структури от данни. Heap се реализира с помощта на масиви или дървета. Разходи за поддръжка, ако са по-малко. По-скъпо за поддръжка. Може да доведе до недостиг на памет, тъй като паметта е ограничена. Няма недостиг на памет, но може да страда от фрагментация на паметта.
често задавани въпроси
В # 1) Стекът по-бърз ли е от Heap?
Отговор: Стекът е по-бърз от купчината, тъй като достъпът е линеен в стека в сравнение с купчината.
В # 2) За какво се използва купчина?
Отговор: Heap се използва най-вече в алгоритми, които намират минималния или най-краткия път между две точки като алгоритъма на Dijkstra, за сортиране с помощта на сортиране на купчина, за реализации на приоритетна опашка (min-heap) и т.н.
В # 3) Какво е купчина? Какви са видовете му?
Отговор: Купчината е йерархична, базирана на дърво структура от данни. Купчината е пълно двоично дърво. Купчините са два вида, т.е. Максимална купчина, в която коренният възел е най-големият сред всички възли; Минимална купчина, при която коренният възел е най-малкият или минимален сред всички ключове.
В # 4) Какви са предимствата на Heap пред стека?
Отговор: Основното предимство на купчината над стека е в купчината, паметта се разпределя динамично и следователно няма ограничение за това колко памет може да се използва. На второ място, само локалните променливи могат да бъдат разпределени в стека, докато ние също можем да разпределим глобални променливи в купчината.
В # 5) Може ли Heap да има дубликати?
Отговор: Да, няма ограничения за наличието на възли с дублиращи се ключове в купчината, тъй като купчината е цялостно двоично дърво и не отговаря на свойствата на бинарното дърво за търсене.
Заключение
В този урок обсъдихме типовете купчина и сортиране на купчинки, като използваме типове купчина. Видяхме и подробното внедряване на неговите типове в Java.
=> Вижте Перфектното ръководство за обучение по Java тук.
Препоръчително четене
- Урок за графики на Java - Как да внедрим структурата на данните за графики
- Въведение в структурите на данни в C ++
- Сортиране на купчини в C ++ с примери
- Структура на данните за дърво и купчина AVL в C ++
- Структура на данните на двоичното дърво в C ++
- Структура на данните за опашката в C ++ с илюстрация
- Структура на данните от циркулярно свързан списък в C ++ с илюстрация
- Основи на Java: Синтаксис на Java, клас Java и основни концепции на Java
