EN Min-haug er definert som en type Heap-datastrukturen er en type binært tre som ofte brukes i informatikk til forskjellige formål, inkludert sortering, søk og organisering av data.
Introduksjon til Min-Heap – Datastruktur og algoritmeopplæring
Formål og brukstilfeller av Min-Heap:
- Implementeringsprioritetskø: En av de primære bruksområdene for heap-datastrukturen er å implementere prioriterte køer.
- Dijkstras algoritme : Dijkstras algoritme er en korteste vei-algoritme som finner den korteste veien mellom to noder i en graf. En min haug kan brukes til å holde styr på de ubesøkte nodene med den minste avstanden fra kildenoden.
- Sortering: En min haug kan brukes som en sorteringsalgoritme for å effektivt sortere en samling av elementer i stigende rekkefølge.
- Medianfunn: En min haug kan brukes til å effektivt finne medianen til en strøm av tall. Vi kan bruke en min haug til å lagre den største halvdelen av tallene og en maks haug til å lagre den mindre halvdelen. Medianen vil være roten til min-haugen.
Min-Heap-datastruktur på forskjellige språk:
1. Min-Heap i C++
En min haug kan implementeres ved å bruke priority_queue container fra Standard Template Library (STL). De priority_queue container er en type containeradapter som gir en måte å lagre elementer i en kølignende datastruktur der hvert element har en prioritet knyttet til seg.
Syntaks :
C++
priority_queue < int, vector , større > minH;>
2. Min-haug i Java
I Java kan en min heap implementeres ved hjelp av Prioritetskø klasse fra java.util-pakken . PriorityQueue-klassen er en prioritetskø som gir en måte å lagre elementer i en kølignende datastruktur der hvert element har en prioritet knyttet til seg.
Syntaks :
Java PriorityQueue minHeap = ny PriorityQueue ();>
3. Min-haug i Python
I Python kan en min heap implementeres ved å bruke heapq modul, som gir funksjoner for implementering av heaps. Nærmere bestemt heapq modulen gir en måte å lage og manipulere haugdatastrukturer.
Syntaks:
Python heap = [] heapify(heap)>
4. Min-haug i C#
I C# kan en min heap implementeres ved å bruke PriorityQueue-klassen fra System.Collections.Generisk navneområde . PriorityQueue-klassen er en prioritetskø som gir en måte å lagre elementer i en kølignende datastruktur der hvert element har en prioritet knyttet til seg.
Syntaks:
C# var minHeap = new PriorityQueue ();>
5. Min-heap i JavaScript
En min haug er et binært tre der hver node har en verdi mindre enn eller lik dens barn. I JavaScript kan du implementere en min haug ved hjelp av en matrise, der det første elementet representerer rotnoden, og barna til en node ved indeksen Jeg ligger på indekser 2i+1 og 2i+2.
Syntaks:
JavaScript const minHeap = new MinHeap();>
Forskjellen mellom Min Heap og Max Heap:
|
| Min haug | Max Heap |
|---|---|---|
| 1. | I en Min-heap må nøkkelen som er tilstede ved rotnoden være mindre enn eller lik blant nøklene som er tilstede på alle dens barn. | I en Max-Heap må nøkkelen som er tilstede ved rotnoden være større enn eller lik blant nøklene som er tilstede på alle dens barn. |
| 2. | I en Min-Heap er minimumsnøkkelelementet til stede ved roten. | I en Max-Heap er det maksimale nøkkelelementet til stede ved roten. |
| 3. | En Min-heap bruker den stigende prioritet. | En Max-Heap bruker synkende prioritet. |
| 4. | I konstruksjonen av en Min-Heap har det minste elementet prioritet. | Ved bygging av en Max-Heap har det største elementet prioritet. |
| 5. | I en Min-heap er det minste elementet det første som blir tatt ut av haugen. forskjellen mellom array og arraylist | I en Max-Heap er det største elementet det første som blir spratt fra haugen. |
Intern implementering av Min-Heap-datastruktur:
EN Min haug er vanligvis representert som en matrise .
- Rotelementet vil være kl Arr[0] .
- For hvilken som helst ith-node Arr[i] :
- Arr[(i -1) / 2] returnerer sin overordnede node.
- Arr[(2 * i) + 1] returnerer venstre underordnet node.
- Arr[(2 * i) + 2] returnerer sin høyre underordnede node.
Den interne implementeringen av Min-Heap krever 3 hovedtrinn:
- Innsetting : For å sette inn et element i min-heapen, legger vi først elementet til slutten av matrisen og justerer deretter heap-egenskapen ved å bytte elementet med dets overordnede gjentatte ganger til det er i riktig posisjon.
- Sletting : For å fjerne minimumselementet fra min-heapen, bytter vi først rotnoden med det siste elementet i arrayet, fjerner det siste elementet, og justerer deretter heap-egenskapen ved å gjentatte ganger bytte elementet med det minste barnet til det er i riktig posisjon.
- Heapify : En heapify-operasjon kan brukes til å lage en min heap fra en usortert matrise.
Operasjoner på Min-heap-datastrukturen og deres implementering:
Her er noen vanlige operasjoner som kan utføres på en heap-datastruktur,
1. Innsetting i Min-Heap-datastruktur :
Elementer kan settes inn i haugen etter en lignende tilnærming som diskutert ovenfor for sletting. Tanken er å:
- Innsettingsoperasjonen i en min-heap involverer følgende trinn:
- Legg til det nye elementet på slutten av haugen, i neste tilgjengelige posisjon på det siste nivået i treet.
- Sammenlign det nye elementet med dets overordnede element. Hvis overordnet er større enn det nye elementet, bytt dem.
- Gjenta trinn 2 til forelderen er mindre enn eller lik det nye elementet, eller til det nye elementet når roten av treet.
- Det nye elementet er nå i sin riktige posisjon i min-heapen, og heap-egenskapen er tilfredsstilt.
Illustrasjon:
Anta at haugen er en min-haug som:
Innsetting i Min-Heap
Implementering av innsettingsoperasjon 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 verdi) { // Legg til det nye elementet på slutten av heapen heap.push_back(value); // Få indeksen til det siste elementet int index = heap.size() - 1; // Sammenlign det nye elementet med dets overordnede element og bytt om // nødvendig while (indeks> 0 && heap[(indeks - 1) / 2]> heap[indeks]) { swap(heap[indeks], heap[(indeks - 1) / 2]); // Flytt oppover i treet til overordnet til gjeldende // elementindeks = (indeks - 1) / 2; } } // Hovedfunksjon for å teste funksjonen insert_min_heap int main() { vektor haug; int verdier[] = { 10, 7, 11, 5, 4, 13 }; int n = størrelse på(verdier) / størrelse på(verdier[0]); for (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 && haug[(indeks - 1) / 2]> haug[indeks]) { swap(haug, indeks, (indeks - 1) / 2); // Flytt oppover i treet til overordnet til gjeldende // elementindeks = (indeks - 1) / 2; } } // Funksjon for å bytte to elementer i en matrise public static void swap(int[] arr, int i, int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } // Hovedfunksjon for å teste insertMinHeap-funksjonen public static void main(String[] args) { int[] heap = new int[6]; int[] verdier = { 10, 7, 11, 5, 4, 13 }; int størrelse = 0; for (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 og haug[(indeks - 1) // 2]> haug[indeks]: haug[indeks], haug[(indeks - 1) // 2] = haug[(indeks - 1) // 2], haug[ indeks] # Flytt opp i treet til overordnet til gjeldende element indeks = (indeks - 1) // 2 haug = [] verdier = [10, 7, 11, 5, 4, 13] for verdi i verdier: insert_min_heap( haug, verdi) print(f'Satt inn {verdi} i min-haugen: {haug}')> 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) { // Legg til det nye elementet til slutten av heapen. Add(value); // Få indeksen til det siste elementet int index = heap.Count - 1; // Sammenlign det nye elementet med dets overordnede element og bytt // om nødvendig while (indeks> 0 && heap[(indeks - 1) / 2]> heap[indeks]) { int temp = heap[indeks]; haug[indeks] = haug[(indeks - 1) / 2]; heap[(indeks - 1) / 2] = temp; // Flytt oppover i treet til overordnet til gjeldende // elementindeks = (indeks - 1) / 2; } } // Hovedfunksjon for å teste InsertMinHeap-funksjonen public static void Main() { Liste haug = ny liste (); int[] verdier = { 10, 7, 11, 5, 4, 13 }; foreach(int verdi i verdier) { InsertMinHeap(heap, verdi); Console.Write('Satt inn ' + verdi + ' i min-haugen: '); foreach(int element i haug) { 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[indeks]) { [heap[indeks], heap[parentIndex]] = [heap[parentIndex], heap[indeks]]; indeks = parentIndex; parentIndex = Math.floor((indeks - 1) / 2); } } // Eksempel på bruk const heap = []; const-verdier = [10, 7, 11, 5, 4, 13]; for (konst verdi av verdier) { insertMinHeap(heap, verdi); console.log(`Satt inn ${value} i min-haugen: ${heap}`); }> Produksjon
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...>
Tidskompleksitet: O(log(n)) ( hvor n er antall elementer i haugen )
Hjelpeplass: På)
2. Sletting i Min-Heap-datastrukturen :
Fjerne det minste elementet (roten) fra min-haugen. Roten erstattes av det siste elementet i haugen, og deretter gjenopprettes haugegenskapen ved å bytte ut den nye roten med det minste barnet til forelderen er mindre enn begge barn eller til den nye roten når en bladnode.
- Erstatt roten eller elementet som skal slettes med det siste elementet.
- Slett det siste elementet fra heapen.
- Siden det siste elementet nå er plassert på posisjonen til rotnoden. Så det kan hende den ikke følger haugeiendommen. Derfor, heapify den siste noden plassert ved posisjonen til roten.
Illustrasjon :
Anta at haugen er en min-haug som:
Min-haug datastruktur
Elementet som skal slettes er root, dvs. 13.
Prosess :
Det siste elementet er 100.
Trinn 1: Erstatt det siste elementet med root, og slett det.
Min-haug datastruktur
Steg 2 : Heapify rot.
Siste haug:
Min-haug datastruktur
Implementering av sletteoperasjon 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 verdi) { // Legg til det nye elementet på slutten av heapen heap.push_back(value); // Få indeksen til det siste elementet int index = heap.size() - 1; // Sammenlign det nye elementet med dets overordnede element og bytt om // nødvendig while (indeks> 0 && heap[(indeks - 1) / 2]> heap[indeks]) { swap(heap[indeks], heap[(indeks - 1) / 2]); // Flytt oppover i treet til overordnet til gjeldende // elementindeks = (indeks - 1) / 2; } } // Funksjon for å slette en node fra min-heap void delete_min_heap(vektor & heap, int verdi) { // Finn indeksen til elementet som skal slettes int index = -1; for (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 haug; int-verdier[] = { 13, 16, 31, 41, 51, 100 }; int n = størrelse på(verdier) / størrelse på(verdier[0]); for (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) { // Legg til det nye elementet på slutten av heap.add(value); // Få indeksen til det siste elementet int index = heap.size() - 1; // Sammenlign det nye elementet med dets overordnede element og bytt // om nødvendig while (indeks> 0 && heap.get((index - 1) / 2)> heap.get(index)) { Collections.swap(heap, index, (indeks - 1) / 2); // Flytt oppover i treet til overordnet til gjeldende // elementindeks = (indeks - 1) / 2; } } // Funksjon for å slette en node fra min-heap public static void deleteMinHeap(List heap, int verdi) { // Finn indeksen til elementet som skal slettes int index = -1; for (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[] verdier = { 13, 16, 31, 41, 51, 100 }; int n = verdier.lengde; for (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 og haug[(indeks - 1) // 2]> haug[indeks]: haug[indeks], haug[(indeks - 1) // 2] = haug[(indeks - 1) // 2], haug[ indeks] indeks = (indeks - 1) // 2 def delete_min_heap(heap, verdi): indeks = -1 for i i området(len(heap)): if heap[i] == verdi: indeks = i break if indeks == -1: returner haug[indeks] = haug[-1] heap.pop() mens True: left_child = 2 * indeks + 1 right_child = 2 * indeks + 2 minste = indeks hvis 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 haug = ny liste (); public void Insert(int verdi) { heap.Add(verdi); int indeks = heap.Count - 1; while (indeks> 0 && haug[(indeks - 1) / 2]> haug[indeks]) { Swap(indeks, (indeks - 1) / 2); indeks = (indeks - 1) / 2; } } public void Delete(int value) { int index = heap.IndexOf(value); if (indeks == -1) { return; } heap[indeks] = heap[heap.Count - 1]; heap.RemoveAt(heap.Count - 1); while (true) { int leftChild = 2 * indeks + 1; int rightChild = 2 * indeks + 2; int minste = indeks; hvis (venstrebarn< 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 && haug[flr]> haug[indeks]; flr = Math.floor((indeks - 1) / 2)) { [heap[indeks], heap[flr]] = [heap[flr], heap[indeks], ]; // Flytt oppover i treet til overordnet til gjeldende elementindeks = Math.floor((index - 1) / 2); } } function deleteMinHeap(heap, value) { // Finn indeksen til elementet som skal slettes la indeks = -1; for (la 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(' '));> Produksjon
Initial heap: 13 16 31 41 51 100 Heap after deleting 13: 16 41 31 100 51>
Tidskompleksitet : O(log n) hvor n er antall elementer i haugen
Hjelpeplass: På)
3. Kikkoperasjon på Min-Heap-datastruktur:
For å få tilgang til minimumselementet (dvs. roten til haugen), returneres verdien til rotnoden. Tidskompleksiteten til kikk i en min-haug er O(1).
Min haug datastruktur
Implementering av Peek-operasjon 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å peak-elementet (dvs. det største 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å peak-elementet (dvs. det største elementet) int peakElement = minHeap.peek(); // Skriv ut peak-elementet System.out.println('Peak-element: ' + 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å peak-elementet (dvs. det minste 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å peak-elementet (dvs. det minste elementet) const peakElement = minHeap.peek(); // Skriv ut toppelementet console.log(`Peak element: ${peakElement}`);> Produksjon
Peak element: 1>
Tidskompleksitet : I en min heap implementert ved hjelp av en matrise eller en liste, kan toppelementet nås i konstant tid, O(1), da det alltid er plassert ved roten av heapen.
I en min haug implementert ved hjelp av et binært tre, kan toppelementet også nås i O(1)-tid, da det alltid er plassert ved roten av treet.
Hjelpeplass: På)
4. Heapify-operasjon på Min-Heap-datastruktur:
En heapify-operasjon kan brukes til å lage en min heap fra en usortert matrise. Dette gjøres ved å starte ved den siste noden uten blader og gjentatte ganger utføre boble ned-operasjonen til alle noder tilfredsstiller heap-egenskapen.
Heapify-operasjon i Min Heap
Implementering av Heapify-operasjon i Min-Heap:
C++ #include #include using namespace std; void minHeapify(vector &arr, int i, int n) { int minste = i; int l = 2*i + 1; int r = 2*i + 2; hvis (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) { // Anta at roten er det minste elementet i utgangspunktet int minste = i; // Beregn indeksene til venstre og høyre underordnede av gjeldende node int l = 2 * i + 1; int r = 2 * i + 2; // Sammenlign det venstre barnet med det gjeldende minste hvis (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 den originale matrisen for (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-haug etter heapify-operasjon: '); // Skriv ut min-haugen etter heapify-operasjon for (int i = 0; i< arr.size(); i++) System.out.print(arr.get(i) + ' '); } }> Python 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 minste = i; int venstre = 2 * i + 1; int høyre = 2 * i + 2; // Sammenlign det venstre barnet med den gjeldende minste noden. hvis (venstre< 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 liste { 10, 5, 15, 2, 20, 30 }; Console.Write('Original array: '); foreach (int num i arr) Console.Write(num + ' '); // Utfør heapify-operasjon på min-heapen. for (int i = arr.Count / 2 - 1; i>= 0; i--) MinHeapify(arr, i, arr.Count); Console.Write('
Min-Heap etter heapify-operasjon: '); 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.lengde); // Skriv ut min-heapen etter heapify-operasjon console.log('Min-Heap etter heapify-operasjon: ' + arr.join(' ')); } // Kall hovedfunksjonen for å starte prosessen main();> Produksjon
Original array: 10 5 15 2 20 30 Min-Heap after heapify operation: 2 5 15 10 20 30>
Tidskompleksiteten til heapify i en min-heap er O(n).
5. Søkeoperasjon på Min-Heap Data Structure:
For å søke etter et element i min-haugen, kan et lineært søk utføres over matrisen som representerer haugen. Imidlertid er tidskompleksiteten til et lineært søk O(n), noe som ikke er effektivt. Derfor er søk ikke en vanlig operasjon i en min haug.
Her er en eksempelkode som viser hvordan du søker etter et element i en min haug ved hjelp av std::finn() :
C++ #include using namespace std; int main() { priority_queue , større > min_haug; // eksempel maks haug min_heap.push(10); min_heap.push(9); min_heap.push(8); min_heap.push(6); min_heap.push(4); int element = 6; // element for å søke etter bool funnet = false; // Kopier min-haugen til en midlertidig kø og søk etter // elementet std::priority_queue , større > temp = min_heap; while (!temp.empty()) { if (temp.top() == element) { found = true; gå i stykker; } temp.pop(); } if (funnet) { 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 = ny PriorityQueue(); min_heap.add( 3); // sett inn elementer i prioritetskøen min_heap.offer(1); min_heap.offer(4); min_heap.offer(1); min_heap.offer(6); int element = 6; // element for å søke etter boolsk funnet = false; // Kopier min-haugen til en midlertidig kø og søk // etter elementet PriorityQueue temp = new PriorityQueue(min_heap); while (!temp.isEmpty()) { if (temp.poll() == element) { found = true; gå i stykker; } } if (funnet) { System.out.println( 'Element funnet i min-haugen.'); } else { System.out.println( 'Element ikke funnet i min-haugen.'); } } }> 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 (); // eksempel min haug minHeap.Enqueue(4); minHeap.Enqueue(6); minHeap.Enqueue(8); minHeap.Enqueue(9); minHeap.Enqueue(10); int element = 6; // element for å søke etter bool funnet = false; // Kopier min-haugen til en midlertidig kø og søk // etter elementet var temp = new PriorityQueue (minHeap); while (temp.Count> 0) { if (temp.Peek() == element) { found = true; gå i stykker; } temp.Dequeue(); } if (funnet) { Console.WriteLine( 'Element funnet i min-haugen.'); } else { Console.WriteLine( 'Element ikke funnet i min-haugen.'); } } }> 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) { funnet = sant; gå i stykker; } temp.dequeue(); } if (funnet) { console.log('Element funnet i min-haugen.'); } else { console.log('Element ikke funnet i min-haugen.'); }> Produksjon
Element found in the min heap.>
Kompleksitetsanalyse :
De tidskompleksitet av dette programmet er O(n log n) , hvor n er antall elementer i prioritetskøen.
Innsettingsoperasjonen har en tidskompleksitet på O(log n) i verste fall fordi haugeiendommen må vedlikeholdes. Søkeoperasjonen innebærer å kopiere prioritetskøen til en midlertidig kø og deretter krysse den midlertidige køen, noe som tar O(n log n) tid i verste fall fordi hvert element må kopieres og poppes fra køen, og prioritetskøen må bygges om for hver operasjon.
De plass kompleksitet av programmet er På) fordi den lagrer n elementer i prioritetskøen og oppretter en midlertidig kø med n elementer.
Anvendelser av Min-Heap-datastruktur:
- Sortering av hauger: Min haug brukes som en nøkkelkomponent i haugsorteringsalgoritme som er en effektiv sorteringsalgoritme med en tidskompleksitet på O(nlogn).
- Prioritetskø: En prioritetskø kan implementeres ved å bruke en min heap-datastruktur der elementet med minimumsverdien alltid er ved roten.
- Dijkstras algoritme: I Dijkstras algoritme brukes en min haug til å lagre toppunktene til grafen med minimumsavstanden fra startpunktet. Toppunktet med minste avstand er alltid ved roten av haugen.
- Huffman-koding: I Huffman-koding brukes en min heap til å implementere en prioritetskø for å bygge en optimal prefikskode for et gitt sett med tegn.
- Slå sammen K sorterte matriser: Gitt K sorterte matriser, kan vi slå dem sammen til en enkelt sortert matrise effektivt ved å bruke en min heap-datastruktur.
Fordeler med Min-heap-datastruktur:
- Effektiv innsetting og sletting : Min haug tillater rask innsetting og sletting av elementer med en tidskompleksitet på O(log n), der n er antall elementer i haugen.
- Effektiv henting av minimumselement: Minimumselementet i en min haug er alltid ved roten av haugen, som kan hentes i O(1) tid.
- Plasseffektiv: Min heap er en kompakt datastruktur som kan implementeres ved hjelp av en matrise eller et binært tre, noe som gjør den plasseffektiv.
- Sortering: Min haug kan brukes til å implementere en effektiv sorteringsalgoritme som haugsortering med en tidskompleksitet på O(n log n).
- Prioritetskø: Min heap kan brukes til å implementere en prioritetskø, hvor elementet med minimum prioritet kan hentes effektivt på O(1) tid.
- Allsidighet: Min heap har flere applikasjoner innen informatikk, inkludert grafalgoritmer, datakomprimering og databasesystemer.
Totalt sett er min heap en nyttig og allsidig datastruktur som tilbyr effektiv drift, plasseffektivitet og har flere applikasjoner innen informatikk.
nettverk og typer nettverk