Преди да започнем, се предполага, че знаете за двоично дърво (в двоично дърво всеки възел съхранява ключ, по-голям от всички ключове в лявото поддърво и по-малко от всички ключове в дясното поддърво ) . Като има предвид, че двоичната купчина е пълно двоично дърво, което отговаря на свойството за подреждане на min-heap or max-heap. Ако не сте запознати с тези понятия, препоръчваме ви да ги разберете като предпоставка. Много начинаещи програмисти могат да се борят с концепцията за Heaps, Min Heaps и Priority Queues. В тази публикация ще се потопим дълбоко, за да видим How купчините са различни от Min-Heaps и How можем да използваме опашки с приоритет за внедряване на Min-Heaps.
Какво е Min Heap?
Min-heap има свойството, че всеки възел на ниво 'n' съхранява стойност, която е по-малка or равна на тази на неговите деца на ниво 'n+1'. Тъй като коренът има стойност, по-малка or равна на неговите деца, които от своя страна имат стойности, по-малки or равни на техните деца, коренът съхранява минимума от всички стойности в дървото.
Пример
Фигура 1: Обикновен min heap
Обърнете внимание, че няма необходима връзка между стойността на възел и тази на неговия събрат нито в min-heap, нито в max-heap. Например, възможно е стойностите за всички възли в лявото поддърво на корена да са по-големи от стойностите за всеки възел на дясното поддърво.
Най-често използваната структура от данни за представяне на Min Heap е прост масив. Като начинаещ не е нужно да бъркате „масив“ с „min-heap“. Можете да го разгледате така, че стойностите на възлите / елементите на min-heap се съхраняват в масив . Точно Howто нямаме ниHowва структура от данни за съхраняване на „ дърво “ в Java и изграждаме „възел“ за него or начина, по който използваме „карта“ за съхраняване на „ графика “.
Фигура 3: Масивно представяне на купчината на фигура 2
Ще демонстрираме How можете просто да получите достъп до родителските, десните or левите дъщерни възли, като използвате следните формули.
Нека minHeap[] е целочислен масив с корен при индекс “ i = 0; ”.
minHeap[(i - 1) / 2] връща родителския възел.
minHeap[(i * 2) + 2] връща десния дъщерен възел.
minHeap[(i * 2) + 1] връща левия дъщерен възел.
Като се има предвид фигура # 2, дадена по-горе, стойността на корен (родител) = 3, ляв дъщерен възел е 13, а десен дъщерен възел = 7.
Внедряване на Min Heap в Java - използване на масиви
Нека да разгледаме основното изпълнение на Heaps, използвайки масив, с индекс като текущата позиция на елемента, който трябва да се добави, и размер като общия размер на масива.
import java.util.Arrays;
public class MinHeap
{
private int[] Heap;
private int index;
private int size;
public MinHeap(int size) {
this.size = size;
this.index = 0;
Heap = new int[size];
}
private int parent(int i) {
return (i - 1) / 2;
}
private int leftChild(int i) {
return (i * 2) + 1;
}
private int rightChild(int i) {
return (i * 2) + 2;
}
private boolean isLeaf(int i) {
if (rightChild(i) >= size || leftChild(i) >= size) {
return true;
}
return false;
}
public void insert(int element) {
if (index >= size) {
return;
}
Heap[index] = element;
int current = index;
while (Heap[current] < Heap[parent(current)]) {
swap(current, parent(current));
current = parent(current);
}
index++;
}
// removes and returns the minimum element from the heap
public int remove() {
// since its a min heap, so root = minimum
int popped = Heap[0];
Heap[0] = Heap[--index];
minHeapify(0);
return popped;
}
// heapify the node at i
private void minHeapify(int i) {
// If the node is a non-leaf node and any of its child is smaller
if (!isLeaf(i)) {
if (Heap[i] > Heap[leftChild(i)] ||
Heap[i] > Heap[rightChild(i)]) {
if (Heap[leftChild(i)] < Heap[rightChild(i)]) {
swap(i, leftChild(i));
minHeapify(leftChild(i));
} else {
swap(i, rightChild(i));
minHeapify(rightChild(i));
}
}
}
}
// builds the min-heap using the minHeapify
public void minHeap() {
for (int i = (index - 1 / 2); i >= 1; i--) {
minHeapify(i);
}
}
// Function to print the contents of the heap
public void printHeap() {
for (int i = 0; i < (index / 2); i++) {
System.out.print("Parent : " + Heap[i]);
if (leftChild(i) < index)
System.out.print(" Left : " + Heap[leftChild(i)]);
if (rightChild(i) < index)
System.out.print(" Right :" + Heap[rightChild(i)]);
System.out.println();
}
}
// swaps two nodes of the heap
private void swap(int x, int y) {
int tmp;
tmp = Heap[x];
Heap[x] = Heap[y];
Heap[y] = tmp;
}
public static void main(String[] arg)
{
MinHeap minHeap = new MinHeap(7);
minHeap.insert(3);
minHeap.insert(13);
minHeap.insert(7);
minHeap.insert(16);
minHeap.insert(21);
minHeap.insert(12);
minHeap.insert(9);
minHeap.minHeap();
System.out.println("The Min Heap is : " + Arrays.toString(minHeap.Heap);
minHeap.printHeap();
System.out.println("\nThe Min Value is : " + minHeap.remove());
System.out.println("\nThe Min Heap is :"+ Arrays.toString(minHeap.Heap));
minHeap.printHeap();
}
}
Приоритетната опашка е специален тип опашка, в която всеки елемент е свързан с приоритет и е поставен според приоритета си. За по-лесно внедряване на min heap, ние използваме класа PriorityQueue java.util.PriorityQueue , предоставен от Java. Ако дадените елементи трябва да бъдат сортирани/поставени по приоритет, тогава се използва приоритетна опашка. Приоритетната опашка е различна от обикновената опашка, тъй като стандартните опашки следват алгоритъма „първи влязъл-първи излязъл“ ( FIFO ), но понякога елементите на опашката трябва да бъдат обработени според приоритета, затова е проектирана опашката с приоритет. Когато добавяте елементи към опашка с приоритет, по подразбиране се изгражда минимална купчина.
Общи операции
Преди да преминем към внедряването, ето няколко общи операции в java.util.PriorityQueue , които трябва да знаете.
add(int element) вмъква посочения елемент в приоритетна опашка.
remove(int element) премахва едно копие на посочения елемент от тази опашка, ако е налице.
peek() извлича, но не премахва главата на тази опашка or връща null, ако опашката е празна.
poll() извлича и премахва главата на тази опашка or връща нула, ако тази опашка е празна.
съдържа() връща „истина“, ако тази опашка съдържа посочения елемент.
size() връща броя на елементите в тази приоритетна опашка/minheap.
Внедряване на Min Heap в Java с помощта на приоритетни опашки
Ето How можете да имплементирате min heap, като използвате приоритетен клас на опашка от java.
import java.util.*;
class MinHeapPriorityQueue {
static PriorityQueue minHeap = new PriorityQueue();
public static void view() {
for (Integer x : minHeap) {
System.out.print(x + " ");
}
System.out.println();
}
public static void main(String args[]) {
// using "add" operation to insert elements
minHeap.add(3);
System.out.print("minHeap.add(3) = ");
view();
minHeap.add(13);
minHeap.add(7);
minHeap.add(16);
minHeap.add(21);
minHeap.add(12);
minHeap.add(9);
// printing Min-Heap
System.out.print("minHeap.view() = ");
view();
// using "peek" method to view the head
System.out.println("minHeap.peek() = " + minHeap.peek());
// using "poll" method to remove and retrieve the head
minHeap.poll();
System.out.print("minHeap.poll() = ");
view();
// using "remove" method to remove specified element
minHeap.remove(7);
System.out.print("minHeap.remove(7) = ");
view();
// Check if an element is present using contains()
boolean elementFound = minHeap.contains(11);
System.out.println("minHeap.contains(11) = " + elementFound);
elementFound = minHeap.contains(16);
System.out.println("minHeap.contains(16) = " + elementFound);
}
}
Минималните купчини се използват широко за извличане на най-малкия елемент в набор от елементи за постоянно време. Има много други applications на тази структура от данни, но можете да изберете всеки метод за прилагане на това. Излишно е да казвам, че трябва да практикувате с търпение, за да се справите добре. Така че нека раздвижим мускулите си и се захващаме за работа!
GO TO FULL VERSION