A Min-Hög definieras som en typ av Högdatastrukturen är en typ av binärt träd som vanligtvis används inom datavetenskap för olika ändamål, inklusive sortering, sökning och organisering av data.
Introduktion till Min-Heap – Självstudier för datastruktur och algoritmer
Syfte och användningsfall av Min-Heap:
- Implementeringsprioritetskö: En av de primära användningsområdena för heapdatastrukturen är att implementera prioritetsköer.
- Dijkstras algoritm : Dijkstras algoritm är en kortaste vägsalgoritm som hittar den kortaste vägen mellan två noder i en graf. En min heap kan användas för att hålla reda på de obesökta noderna med det minsta avståndet från källnoden.
- Sortering: En min-hög kan användas som en sorteringsalgoritm för att effektivt sortera en samling element i stigande ordning.
- Medianfynd: En min hög kan användas för att effektivt hitta medianen för en ström av tal. Vi kan använda en min hög för att lagra den större hälften av siffrorna och en maxhög för att lagra den mindre hälften. Medianen kommer att vara roten till minhögen.
Min-Heap Datastruktur på olika språk:
1. Min-Heap i C++
En min heap kan implementeras med hjälp av priority_queue behållare från Standard Template Library (STL). De priority_queue container är en typ av containeradapter som tillhandahåller ett sätt att lagra element i en köliknande datastruktur där varje element har en prioritet kopplad till sig.
Syntax :
C++
priority_queue < int, vector , större > minH;>
2. Min-Heap i Java
I Java kan en min heap implementeras med hjälp av Prioritetskö klass från java.util-paketet . Klassen PriorityQueue är en prioritetskö som tillhandahåller ett sätt att lagra element i en köliknande datastruktur där varje element har en prioritet kopplad till sig.
Syntax :
Java PriorityQueue minHeap = ny PriorityQueue ();>
3. Min-Heap i Python
I Python kan en min heap implementeras med hjälp av heapq modul, som tillhandahåller funktioner för att implementera heaps. Närmare bestämt heapq modulen ger ett sätt att skapa och manipulera högdatastrukturer.
Syntax:
Pytonorm heap = [] heapify(heap)>
4. Min-Heap i C#
I C# kan en min heap implementeras med klassen PriorityQueue från System.Collections.Generiskt namnområde . Klassen PriorityQueue är en prioritetskö som tillhandahåller ett sätt att lagra element i en köliknande datastruktur där varje element har en prioritet kopplad till sig.
Syntax:
C# var minHeap = new PriorityQueue ();>
5. Min-hög i JavaScript
En min-hög är ett binärt träd där varje nod har ett värde som är mindre än eller lika med dess barn. I JavaScript kan du implementera en min-hög med hjälp av en array, där det första elementet representerar rotnoden och barnen till en nod vid index i finns vid index 2i+1 och 2i+2.
Syntax:
nätverk och internetJavaScript
const minHeap = new MinHeap();>
Skillnaden mellan Min Heap och Max Heap:
|
| Min hög | Max Heap |
|---|---|---|
| 1. q1 q2 q3 q4 | I en Min-Heap måste nyckeln som finns vid rotnoden vara mindre än eller lika med bland nycklarna som finns hos alla dess underordnade. | I en Max-Heap måste nyckeln som finns vid rotnoden vara större än eller lika med bland nycklarna som finns hos alla dess underordnade. |
| 2. | I en Min-Heap finns det minsta nyckelelementet i roten. | I en Max-Heap finns det maximala nyckelelementet vid roten. |
| 3. | En Min-Heap använder stigande prioritet. | En Max-Heap använder den fallande prioriteten. |
| 4. | I konstruktionen av en Min-Heap har det minsta elementet prioritet. | I konstruktionen av en Max-Heap har det största elementet prioritet. |
| 5. | I en Min-Heap är det minsta elementet det första som tas bort från högen. | I en Max-Heap är det största elementet det första som tas bort från högen. |
Intern implementering av Min-Heap-datastruktur:
A Min heap representeras vanligtvis som en array .
- Rotelementet kommer att vara kl Arr[0] .
- För vilken ith-nod som helst Arr[i] :
- Arr[(i -1) / 2] returnerar sin överordnade nod.
- Arr[(2 * i) + 1] returnerar dess vänstra underordnade nod.
- Arr[(2 * i) + 2] returnerar sin högra underordnade nod.
Den interna implementeringen av Min-Heap kräver tre huvudsteg:
- Införande : För att infoga ett element i min-högen lägger vi först till elementet i slutet av arrayen och justerar sedan heap-egenskapen genom att upprepade gånger byta elementet med dess överordnade tills det är i rätt position.
- Radering : För att ta bort minimumelementet från min-högen byter vi först rotnoden med det sista elementet i arrayen, tar bort det sista elementet och justerar sedan heap-egenskapen genom att upprepade gånger byta elementet med dess minsta underordnade tills det är i rätt position.
- Heapify : En heapify-operation kan användas för att skapa en min heap från en osorterad array.
Operationer på Min-heap-datastruktur och deras implementering:
Här är några vanliga operationer som kan utföras på en heapdatastruktur,
1. Infogning i Min-Heap Data Structure :
Element kan infogas i högen enligt ett liknande tillvägagångssätt som diskuterats ovan för radering. Tanken är att:
- Insättningsoperationen i en min-hög innefattar följande steg:
- Lägg till det nya elementet i slutet av högen, i nästa tillgängliga position i trädets sista nivå.
- Jämför det nya elementet med dess överordnade. Om föräldern är större än det nya elementet, byt ut dem.
- Upprepa steg 2 tills föräldern är mindre än eller lika med det nya elementet, eller tills det nya elementet når roten av trädet.
- Det nya elementet är nu i sin korrekta position i min-högen, och heap-egenskapen är uppfylld.
Illustration:
Anta att högen är en min-hög som:
spärrade nummerInsättning i Min-Heap
Implementering av insättningsoperation i Min-Heap:
C++ #include #include using namespace std; // Function to insert a new element into the min-heap void insert_min_heap(vector & heap, int value) { // Lägg till det nya elementet i slutet av heapen heap.push_back(value); // Hämta indexet för det sista elementet int index = heap.size() - 1; // Jämför det nya elementet med dess överordnade och byt om // behövs while (index> 0 && heap[(index - 1) / 2]> heap[index]) { swap(heap[index], heap[(index - 1) / 2]); // Flytta uppåt i trädet till föräldern för det aktuella // element index = (index - 1) / 2; } } // Huvudfunktion för att testa funktionen insert_min_heap int main() { vektor högen; int värden[] = { 10, 7, 11, 5, 4, 13 }; int n = storlek på(värden) / storlek på(värden[0]); för (int i = 0; i< n; i++) { insert_min_heap(heap, values[i]); cout << 'Inserted ' << values[i] << ' into the min-heap: '; for (int j = 0; j < heap.size(); j++) { cout << heap[j] << ' '; } cout << endl; } return 0; }>
Java import java.util.*; public class GFG { // Function to insert a new element into the min-heap public static void insertMinHeap(int[] heap, int size, int value) { // Add the new element to the end of the heap heap[size] = value; // Get the index of the last element int index = size; // Compare the new element with its parent and swap // if necessary while (index>0 && heap[(index - 1) / 2]> heap[index]) { swap(heap, index, (index - 1) / 2); // Flytta uppåt i trädet till föräldern för det aktuella // element index = (index - 1) / 2; } } // Funktion för att byta två element i en array public static void swap(int[] arr, int i, int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } // Huvudfunktion för att testa insertMinHeap-funktionen public static void main(String[] args) { int[] heap = new int[6]; int[] värden = { 10, 7, 11, 5, 4, 13 }; int storlek = 0; för (int i = 0; i< values.length; i++) { insertMinHeap(heap, size, values[i]); size++; System.out.print('Inserted ' + values[i] + ' into the min-heap: '); for (int j = 0; j < size; j++) { System.out.print(heap[j] + ' '); } System.out.println(); } } }> Python3 def insert_min_heap(heap, value): # Add the new element to the end of the heap heap.append(value) # Get the index of the last element index = len(heap) - 1 # Compare the new element with its parent and swap if necessary while index>0 och heap[(index - 1) // 2]> heap[index]: heap[index], heap[(index - 1) // 2] = heap[(index - 1) // 2], heap[ index] # Flytta uppåt i trädet till föräldern för det aktuella elementet index = (index - 1) // 2 heap = [] värden = [10, 7, 11, 5, 4, 13] för värde i värden: insert_min_heap( heap, value) print(f'Infogat {värde} i min-högen: {hög}')> C# using System; using System.Collections.Generic; public class Program { // Function to insert a new element into the min-heap static void InsertMinHeap(List heap, int value) { // Lägg till det nya elementet i slutet av heapen. Add(value); // Få indexet för det sista elementet int index = heap.Count - 1; // Jämför det nya elementet med dess överordnade och byt // om nödvändigt while (index> 0 && heap[(index - 1) / 2]> heap[index]) { int temp = heap[index]; heap[index] = heap[(index - 1) / 2]; heap[(index - 1) / 2] = temp; // Flytta uppåt i trädet till föräldern för det aktuella // element index = (index - 1) / 2; } } // Huvudfunktion för att testa InsertMinHeap-funktionen public static void Main() { List heap = ny lista (); int[] värden = { 10, 7, 11, 5, 4, 13 }; foreach(int värde i värden) { InsertMinHeap(hög, värde); Console.Write('Infogat ' + värde + ' i min-högen: '); foreach(int element i heap) { Console.Write(element + ' '); } Console.WriteLine(); } } }> Javascript function insertMinHeap(heap, value) { heap.push(value); let index = heap.length - 1; let parentIndex = Math.floor((index - 1) / 2); while (index>0 && heap[parentIndex]> heap[index]) { [heap[index], heap[parentIndex]] = [heap[parentIndex], heap[index]]; index = parentIndex; parentIndex = Math.floor((index - 1) / 2); } } // Exempel på användning const heap = []; const värden = [10, 7, 11, 5, 4, 13]; for (konst värde för värden) { insertMinHeap(hög, värde); console.log(`Infogade ${value} i min-heapen: ${heap}`); }> Produktion
Inserted 10 into the min-heap: 10 Inserted 7 into the min-heap: 7 10 Inserted 11 into the min-heap: 7 10 11 Inserted 5 into the min-heap: 5 7 11 10 Inserted 4 into the min-heap: 4 5 11 10 7 Inser...>
Tidskomplexitet: O(log(n)) ( där n är antalet element i högen )
Hjälputrymme: På)
2. Borttagning i Min-Heap Data Structure :
Ta bort det minsta elementet (roten) från minhögen. Roten ersätts av det sista elementet i högen, och sedan återställs heap-egenskapen genom att byta ut den nya roten med dess minsta underordnade tills föräldern är mindre än båda barnen eller tills den nya roten når en lövnod.
- Ersätt roten eller elementet som ska raderas med det sista elementet.
- Ta bort det sista elementet från högen.
- Eftersom det sista elementet nu är placerat vid positionen för rotnoden. Så det kanske inte följer högegenskapen. Förhöj därför den sista noden placerad vid rotens position.
Illustration :
Anta att högen är en min-hög som:
Min-Heap-datastruktur
Elementet som ska raderas är root, dvs 13.
Bearbeta :
Det sista elementet är 100.
Steg 1: Ersätt det sista elementet med root och ta bort det.
Min-Heap-datastruktur
Steg 2 : Heapify rot.
Sista högen:
Min-Heap-datastruktur
latex teckenstorlek
Implementering av raderingsoperation i Min-Heap:
C++ #include #include using namespace std; // Function to insert a new element into the min-heap void insert_min_heap(vector & heap, int value) { // Lägg till det nya elementet i slutet av heapen heap.push_back(value); // Hämta indexet för det sista elementet int index = heap.size() - 1; // Jämför det nya elementet med dess förälder och byt om // behövs while (index> 0 && heap[(index - 1) / 2]> heap[index]) { swap(heap[index], heap[(index - 1) / 2]); // Flytta uppåt i trädet till föräldern för det aktuella // element index = (index - 1) / 2; } } // Funktion för att ta bort en nod från min-högen void delete_min_heap(vektor & heap, int värde) { // Hitta indexet för elementet som ska raderas int index = -1; för (int i = 0; i< heap.size(); i++) { if (heap[i] == value) { index = i; break; } } // If the element is not found, return if (index == -1) { return; } // Replace the element to be deleted with the last // element heap[index] = heap[heap.size() - 1]; // Remove the last element heap.pop_back(); // Heapify the tree starting from the element at the // deleted index while (true) { int left_child = 2 * index + 1; int right_child = 2 * index + 2; int smallest = index; if (left_child < heap.size() && heap[left_child] < heap[smallest]) { smallest = left_child; } if (right_child < heap.size() && heap[right_child] < heap[smallest]) { smallest = right_child; } if (smallest != index) { swap(heap[index], heap[smallest]); index = smallest; } else { break; } } } // Main function to test the insert_min_heap and // delete_min_heap functions int main() { vector högen; int värden[] = { 13, 16, 31, 41, 51, 100 }; int n = storlek på(värden) / storlek på(värden[0]); för (int i = 0; i< n; i++) { insert_min_heap(heap, values[i]); } cout << 'Initial heap: '; for (int j = 0; j < heap.size(); j++) { cout << heap[j] << ' '; } cout << endl; delete_min_heap(heap, 13); cout << 'Heap after deleting 13: '; for (int j = 0; j < heap.size(); j++) { cout << heap[j] << ' '; } cout << endl; return 0; }>
Java import java.util.*; public class GFG { // Function to insert a new element into the min-heap public static void insertMinHeap(List heap, int value) { // Lägg till det nya elementet i slutet av heapen heap.add(value); // Hämta indexet för det sista elementet int index = heap.size() - 1; // Jämför det nya elementet med dess överordnade och byt // om nödvändigt while (index> 0 && heap.get((index - 1) / 2)> heap.get(index)) { Collections.swap(heap, index, (index - 1)/2); // Flytta uppåt i trädet till föräldern för det aktuella // element index = (index - 1) / 2; } } // Funktion för att ta bort en nod från min-heap public static void deleteMinHeap(List heap, int value) { // Hitta indexet för elementet som ska raderas int index = -1; för (int i = 0; i< heap.size(); i++) { if (heap.get(i) == value) { index = i; break; } } // If the element is not found, return if (index == -1) { return; } // Replace the element to be deleted with the last // element heap.set(index, heap.get(heap.size() - 1)); // Remove the last element heap.remove(heap.size() - 1); // Heapify the tree starting from the element at the // deleted index while (true) { int leftChild = 2 * index + 1; int rightChild = 2 * index + 2; int smallest = index; if (leftChild < heap.size() && heap.get(leftChild) < heap.get(smallest)) { smallest = leftChild; } if (rightChild < heap.size() && heap.get(rightChild) < heap.get(smallest)) { smallest = rightChild; } if (smallest != index) { Collections.swap(heap, index, smallest); index = smallest; } else { break; } } } // Main function to test the insertMinHeap and // deleteMinHeap functions public static void main(String[] args) { List heap = ny ArrayList (); int[] värden = { 13, 16, 31, 41, 51, 100 }; int n = värden.längd; för (int i = 0; i< n; i++) { insertMinHeap(heap, values[i]); } System.out.print('Initial heap: '); for (int j = 0; j < heap.size(); j++) { System.out.print(heap.get(j) + ' '); } System.out.println(); deleteMinHeap(heap, 13); System.out.print('Heap after deleting 13: '); for (int j = 0; j < heap.size(); j++) { System.out.print(heap.get(j) + ' '); } System.out.println(); } }> Python3 def insert_min_heap(heap, value): heap.append(value) index = len(heap) - 1 while index>0 och heap[(index - 1) // 2]> heap[index]: heap[index], heap[(index - 1) // 2] = heap[(index - 1) // 2], heap[ index] index = (index - 1) // 2 def delete_min_heap(heap, värde): index = -1 för i i intervallet(len(heap)): if heap[i] == värde: index = i break if index == -1: returnera heap[index] = heap[-1] heap.pop() medan True: left_child = 2 * index + 1 right_child = 2 * index + 2 minsta = index if left_child< len(heap) and heap[left_child] < heap[smallest]: smallest = left_child if right_child < len(heap) and heap[right_child] < heap[smallest]: smallest = right_child if smallest != index: heap[index], heap[smallest] = heap[smallest], heap[index] index = smallest else: break heap = [] values = [13, 16, 31, 41, 51, 100] for value in values: insert_min_heap(heap, value) print('Initial heap:', heap) delete_min_heap(heap, 13) print('Heap after deleting 13:', heap)> C# using System; using System.Collections.Generic; class MinHeap { private List heap = ny lista (); public void Insert(int value) { heap.Add(value); int index = heap.Count - 1; while (index> 0 && heap[(index - 1) / 2]> heap[index]) { Swap(index, (index - 1) / 2); index = (index - 1) / 2; } } public void Delete(int value) { int index = heap.IndexOf(value); if (index == -1) { return; } hög[index] = hög[hög.Antal - 1]; heap.RemoveAt(heap.Count - 1); while (true) { int leftChild = 2 * index + 1; int rightChild = 2 * index + 2; int minsta = index; om (vänsterbarn< heap.Count && heap[leftChild] < heap[smallest]) { smallest = leftChild; } if (rightChild < heap.Count && heap[rightChild] < heap[smallest]) { smallest = rightChild; } if (smallest != index) { Swap(index, smallest); index = smallest; } else { break; } } } private void Swap(int i, int j) { int temp = heap[i]; heap[i] = heap[j]; heap[j] = temp; } public void Print() { for (int i = 0; i < heap.Count; i++) { Console.Write(heap[i] + ' '); } Console.WriteLine(); } } class Program { static void Main(string[] args) { MinHeap heap = new MinHeap(); int[] values = { 13, 16, 31, 41, 51, 100 }; for (int i = 0; i < values.Length; i++) { heap.Insert(values[i]); } Console.Write('Initial heap: '); heap.Print(); heap.Delete(13); Console.Write('Heap after deleting 13: '); heap.Print(); } }> Javascript function insertMinHeap(heap, value) { // Add the new element to the end of the heap heap.push(value); // Get the index of the last element let index = heap.length - 1; // Compare the new element with its parent and swap if necessary for (let flr = Math.floor((index - 1) / 2); index>0 && hög[flr]> hög[index]; flr = Math.floor((index - 1) / 2)) { [hög[index], hög[flr]] = [hög[flr], hög[index], ]; // Flytta uppåt i trädet till det överordnade elementet index = Math.floor((index - 1) / 2); } } function deleteMinHeap(heap, value) { // Hitta indexet för elementet som ska raderas låt index = -1; för (låt i = 0; i< heap.length; i++) { if (heap[i] == value) { index = i; break; } } // If the element is not found, return if (index == -1) { return; } // Replace the element to be deleted with the last element heap[index] = heap[heap.length - 1]; // Remove the last element heap.pop(); // Heapify the tree starting from the element at the deleted index while (true) { let left_child = 2 * index + 1; let right_child = 2 * index + 2; let smallest = index; if (left_child < heap.length && heap[left_child] < heap[smallest]) { smallest = left_child; } if (right_child < heap.length && heap[right_child] < heap[smallest]) { smallest = right_child; } if (smallest != index) { [heap[index], heap[smallest]] = [heap[smallest], heap[index]]; index = smallest; } else { break; } } } // Main function to test the insertMinHeap and deleteMinHeap functions let heap = []; let values = [13, 16, 31, 41, 51, 100]; for (let i = 0; i < values.length; i++) { insertMinHeap(heap, values[i]); } console.log('Initial heap: ' + heap.join(' ')); deleteMinHeap(heap, 13); console.log('Heap after deleting 13: ' + heap.join(' '));> Produktion
Initial heap: 13 16 31 41 51 100 Heap after deleting 13: 16 41 31 100 51>
Tidskomplexitet : O(log n) där n är antalet element i högen
Hjälputrymme: På)
3. Peek operation på Min-Heap Data Structure:
För att komma åt minimielementet (d.v.s. roten av högen) returneras värdet på rotnoden. Tidskomplexiteten för titt i en min-hög är O(1).
Min Heap-datastruktur
Implementering av Peek-operation i Min-Heap:
C++ #include #include #include using namespace std; int main() { // Create a max heap with some elements using a // priority_queue priority_queue , större > minHeap; minHeap.push(9); minHeap.push(8); minHeap.push(7); minHeap.push(6); minHeap.push(5); minHeap.push(4); minHeap.push(3); minHeap.push(2); minHeap.push(1); // Få toppelementet (dvs det största elementet) int peakElement = minHeap.top(); // Skriv ut peak element cout<< 'Peak element: ' << peakElement << std::endl; return 0; }> Java import java.util.PriorityQueue; public class GFG { public static void main(String[] args) { // Create a max heap with some elements using a // PriorityQueue PriorityQueue minHeap = new PriorityQueue(); minHeap.add(9); minHeap.add(8); minHeap.add(7); minHeap.add(6); minHeap.add(5); minHeap.add(4); minHeap.add(3); minHeap.add(2); minHeap.add(1); // Få toppelementet (dvs det största elementet) int peakElement = minHeap.peek(); // Skriv ut toppelementet System.out.println('Peakelement: ' + peakElement); } }> Python3 import heapq # Create a min heap with some elements using a list min_heap = [9, 8, 7, 6, 5, 4, 3, 2, 1] heapq.heapify(min_heap) # Get the peak element (i.e., the smallest element) peak_element = heapq.nsmallest(1, min_heap)[0] # Print the peak element print('Peak element:', peak_element)> C# using System; using System.Collections.Generic; public class GFG { public static void Main() { // Create a min heap with some elements using a // PriorityQueue var minHeap = new PriorityQueue (); minHeap.Enqueue(9); minHeap.Enqueue(8); minHeap.Enqueue(7); minHeap.Enqueue(6); minHeap.Enqueue(5); minHeap.Enqueue(4); minHeap.Enqueue(3); minHeap.Enqueue(2); minHeap.Enqueue(1); // Få toppelementet (dvs det minsta elementet) int peakElement = minHeap.Peek(); // Skriv ut toppelementet Console.WriteLine('Peak element: ' + peakElement); } }> Javascript const PriorityQueue = require('fast-priority-queue'); // Create a min heap with some elements using a PriorityQueue const minHeap = new PriorityQueue((a, b) =>a - b); minHeap.add(9); minHeap.add(8); minHeap.add(7); minHeap.add(6); minHeap.add(5); minHeap.add(4); minHeap.add(3); minHeap.add(2); minHeap.add(1); // Få toppelementet (dvs det minsta elementet) const peakElement = minHeap.peek(); // Skriv ut toppelementet console.log(`Peak element: ${peakElement}`);> Produktion
Peak element: 1>
Tidskomplexitet : I en min-hög implementerad med hjälp av en array eller en lista, kan toppelementet nås i konstant tid, O(1), eftersom det alltid är beläget vid roten av högen.
I en min-hög implementerad med ett binärt träd, kan toppelementet också nås i O(1)-tid, eftersom det alltid är beläget vid roten av trädet.
Hjälputrymme: På)
4. Heapify-operation på Min-Heap-datastruktur:
En heapify-operation kan användas för att skapa en min heap från en osorterad array. Detta görs genom att börja vid den sista icke-bladsnoden och upprepade gånger utföra bubbla ner-operationen tills alla noder uppfyller heap-egenskapen.
Heapify-operation i Min Heap
Implementering av Heapify-operation i Min-Heap:
C++ #include #include using namespace std; void minHeapify(vector &arr, int i, int n) { int minsta = i; int l = 2*i + 1; int r = 2*i + 2; om (l< n && arr[l] < arr[smallest]) smallest = l; if (r < n && arr[r] < arr[smallest]) smallest = r; if (smallest != i) { swap(arr[i], arr[smallest]); minHeapify(arr, smallest, n); } } int main() { vector arr = {10, 5, 15, 2, 20, 30}; cout<< 'Original array: '; for (int i = 0; i < arr.size(); i++) cout << arr[i] << ' '; // Perform heapify operation on min-heap for (int i = arr.size()/2 - 1; i>= 0; i--) minHeapify(arr, i, arr.size()); cout<< '
Min-Heap after heapify operation: '; for (int i = 0; i < arr.size(); i++) cout << arr[i] << ' '; return 0; }>
Java // Java code of Heapify operation in Min-Heap import java.util.Arrays; import java.util.List; public class Main { // Function to maintain the min-heap property of the heap rooted at index 'i' public static void minHeapify(List arr, int i, int n) { // Antag att roten är det minsta elementet initialt int minsta = i; // Beräkna indexen för vänster och höger underordnad av den aktuella noden int l = 2 * i + 1; int r = 2 * i + 2; // Jämför det vänstra barnet med det nuvarande minsta om (l< n && arr.get(l) < arr.get(smallest)) smallest = l; // Compare the right child with the current smallest if (r < n && arr.get(r) < arr.get(smallest)) smallest = r; // If the current node is not the smallest, swap it with the smallest child if (smallest != i) { int temp = arr.get(i); arr.set(i, arr.get(smallest)); arr.set(smallest, temp); // Recursively heapify the subtree rooted at the smallest child minHeapify(arr, smallest, n); } } public static void main(String[] args) { // Create a list representing the array List arr = Arrays.asList(10, 5, 15, 2, 20, 30); System.out.print('Original array: '); // Skriv ut originalmatrisen för (int i = 0; i< arr.size(); i++) System.out.print(arr.get(i) + ' '); // Perform heapify operation on the min-heap // Start from the last non-leaf node and go up to the root of the tree for (int i = arr.size() / 2 - 1; i>= 0; i--) minHeapify(arr, i, arr.size()); System.out.print('
Min-Heap efter heapify-operation: '); // Skriv ut min-högen efter heapify-operation för (int i = 0; i< arr.size(); i++) System.out.print(arr.get(i) + ' '); } }> Pytonorm def minHeapify(arr, i, n): smallest = i left = 2 * i + 1 right = 2 * i + 2 if left < n and arr[left] < arr[smallest]: smallest = left if right < n and arr[right] < arr[smallest]: smallest = right if smallest != i: arr[i], arr[smallest] = arr[smallest], arr[i] minHeapify(arr, smallest, n) if __name__ == '__main__': arr = [10, 5, 15, 2, 20, 30] print('Original array:', arr) # Perform heapify operation on a min-heap for i in range(len(arr) // 2 - 1, -1, -1): minHeapify(arr, i, len(arr)) print('Min-Heap after heapify operation:', arr)> C# using System; using System.Collections.Generic; class GFG { // Function to perform the minHeapify operation on a min-heap. static void MinHeapify(List arr, int i, int n) { int minsta = i; int vänster = 2 * i + 1; int höger = 2 * i + 2; // Jämför det vänstra barnet med den aktuella minsta noden. om (vänster< n && arr[left] < arr[smallest]) smallest = left; // Compare the right child with the current smallest node. if (right < n && arr[right] < arr[smallest]) smallest = right; // If the current node is not the smallest // swap it with the smallest child. if (smallest != i) { int temp = arr[i]; arr[i] = arr[smallest]; arr[smallest] = temp; // Recursively call minHeapify on the affected subtree. MinHeapify(arr, smallest, n); } } static void Main(string[] args) { List arr = ny lista { 10, 5, 15, 2, 20, 30 }; Console.Write('Original array: '); foreach (int num i arr) Console.Write(num + ' '); // Utför heapify-operation på min-heapen. för (int i = arr.Count / 2 - 1; i>= 0; i--) MinHeapify(arr, i, arr.Count); Console.Write('
Min-Heap efter heapify-operation: '); foreach (int num i arr) Console.Write(num + ' '); } }> Javascript // Define a function to perform min-heapify operation on an array function minHeapify(arr, i, n) { let smallest = i; let l = 2 * i + 1; let r = 2 * i + 2; // Check if left child is smaller than the current smallest element if (l < n && arr[l] < arr[smallest]) smallest = l; // Check if right child is smaller than the current smallest element if (r < n && arr[r] < arr[smallest]) smallest = r; // If the smallest element is not the current element, swap them if (smallest !== i) { [arr[i], arr[smallest]] = [arr[smallest], arr[i]]; minHeapify(arr, smallest, n); } } // Main function function main() { const arr = [10, 5, 15, 2, 20, 30]; // Print the original array console.log('Original array: ' + arr.join(' ')); // Perform heapify operation on the min-heap for (let i = Math.floor(arr.length / 2) - 1; i>= 0; i--) minHeapify(arr, i, arr.längd); // Skriv ut min-högen efter heapify-operation console.log('Min-Heap efter heapify-operation: ' + arr.join(' ')); } // Anropa huvudfunktionen för att starta processen main();> Produktion
Original array: 10 5 15 2 20 30 Min-Heap after heapify operation: 2 5 15 10 20 30>
Tidskomplexiteten för heapify i en min-heap är O(n).
5. Sökoperation på Min-Heap Data Structure:
För att söka efter ett element i min-högen kan en linjär sökning utföras över arrayen som representerar högen. Emellertid är tidskomplexiteten för en linjär sökning O(n), vilket inte är effektivt. Därför är sökning inte en vanlig operation i en min hög.
Här är en exempelkod som visar hur man söker efter ett element i en min hög med std::find() :
C++ #include using namespace std; int main() { priority_queue , större > min_hög; // exempel max heap min_heap.push(10); min_heap.push(9); min_heap.push(8); min_heap.push(6); min_heap.push(4); int element = 6; // element för att söka efter bool found = false; // Kopiera min-högen till en tillfällig kö och sök efter // elementet std::priority_queue , större > temp = min_heap; while (!temp.empty()) { if (temp.top() == element) { found = true; ha sönder; } temp.pop(); } if (hittad) { std::cout<< 'Element found in the min heap.' << std::endl; } else { std::cout << 'Element not found in the min heap.' << std::endl; } return 0; }> Java import java.util.PriorityQueue; public class GFG { public static void main(String[] args) { PriorityQueue min_heap = new PriorityQueue(); min_heap.add( 3); // infoga element i prioritetskön min_heap.offer(1); min_heap.offer(4); min_heap.offer(1); min_heap.offer(6); int element = 6; // element för att söka efter boolean found = false; // Kopiera min-högen till en tillfällig kö och sök // efter elementet PriorityQueue temp = new PriorityQueue(min_heap); while (!temp.isEmpty()) { if (temp.poll() == element) { found = true; ha sönder; } } if (hittad) { System.out.println( 'Element hittat i minhögen.'); } else { System.out.println( 'Element hittades inte i minhögen.'); } } }> Python3 import heapq min_heap = [1, 2, 3, 5, 6, 7, 8, 10] # example min heap heapq.heapify(min_heap) element = 6 # element to search for found = False # Copy the min heap to a temporary list and search for the element temp = list(min_heap) while temp: if heapq.heappop(temp) == element: found = True break if found: print('Element found in the min heap.') else: print('Element not found in the min heap.')> C# using System; using System.Collections.Generic; public class GFG { public static void Main() { var minHeap = new PriorityQueue (); // exempel min heap minHeap.Enqueue(4); minHeap.Enqueue(6); minHeap.Enqueue(8); minHeap.Enqueue(9); minHeap.Enqueue(10); int element = 6; // element för att söka efter bool found = false; // Kopiera min-högen till en tillfällig kö och sök // efter elementet var temp = new PriorityQueue (minHög); while (temp.Count> 0) { if (temp.Peek() == element) { found = true; ha sönder; } temp.Dequeue(); } if (found) { Console.WriteLine( 'Element hittat i minhögen.'); } else { Console.WriteLine( 'Element hittades inte i minhögen.'); } } }> Javascript // Example min heap let minHeap = new PriorityQueue(); minHeap.enqueue(4); minHeap.enqueue(6); minHeap.enqueue(8); minHeap.enqueue(9); minHeap.enqueue(10); let element = 6; // Element to search for let found = false; // Copy the min heap to a temporary queue and search for the element let temp = new PriorityQueue(minHeap); while (temp.size()>0) { if (temp.peek() == element) { found = true; ha sönder; } temp.dequeue(); } if (found) { console.log('Element hittat i min-högen.'); } else { console.log('Element hittades inte i min-högen.'); }> Produktion
Element found in the min heap.>
Komplexitetsanalys :
De tidskomplexitet av detta program är O(n log n) , var n är antalet element i prioritetskön.
Insättningsoperationen har en tidskomplexitet på O(log n) i värsta fall eftersom högfastigheten behöver underhållas. Sökoperationen innebär att prioritetskön kopieras till en tillfällig kö och sedan korsas den tillfälliga kön, vilket tar O(n log n) tid i värsta fall eftersom varje element måste kopieras och poppas från kön, och prioritetskön måste byggas om för varje operation.
De rymdkomplexitet av programmet är På) eftersom den lagrar n element i prioritetskön och skapar en tillfällig kö med n element.
Tillämpningar av Min-Heap Data Structure:
- Hög sortering: Min heap används som en nyckelkomponent i heap sorteringsalgoritm som är en effektiv sorteringsalgoritm med en tidskomplexitet på O(nlogn).
- Prioriterad kö: En prioritetskö kan implementeras med en min heap-datastruktur där elementet med det lägsta värdet alltid är i roten.
- Dijkstras algoritm: I Dijkstras algoritm används en min-hög för att lagra grafens hörn med det minsta avståndet från startpunkten. Spetsen med minsta avstånd är alltid vid roten av högen.
- Huffman kodning: I Huffman-kodning används en min-hög för att implementera en prioritetskö för att bygga en optimal prefixkod för en given uppsättning tecken.
- Slå samman K sorterade arrayer: Med tanke på K sorterade arrayer kan vi slå samman dem till en enda sorterad array effektivt med hjälp av en min heap-datastruktur.
Fördelar med Min-heap datastruktur:
- Effektiv insättning och radering : Min hög tillåter snabb insättning och radering av element med en tidskomplexitet på O(log n), där n är antalet element i högen.
- Effektiv hämtning av minsta element: Minsta element i en min-hög är alltid i roten av högen, som kan hämtas i O(1)-tid.
- Utrymmeseffektiv: Min heap är en kompakt datastruktur som kan implementeras med hjälp av en array eller ett binärt träd, vilket gör den utrymmeseffektiv.
- Sortering: Min heap kan användas för att implementera en effektiv sorteringsalgoritm såsom heapsortering med en tidskomplexitet på O(n log n).
- Prioriterad kö: Min heap kan användas för att implementera en prioritetskö, där elementet med lägsta prioritet kan hämtas effektivt på O(1) tid.
- Mångsidighet: Min heap har flera applikationer inom datavetenskap, inklusive grafalgoritmer, datakomprimering och databassystem.
Sammantaget är min heap en användbar och mångsidig datastruktur som erbjuder effektiv drift, utrymmeseffektivitet och har flera tillämpningar inom datavetenskap.