ÚVOD DO MIN-HEAP – VÝUKOVÉ PROGRAMY PRO DATOVOU STRUKTURU A ALGORITMUS

A Min-Hromad je definován jako typ Struktura dat haldy je typ binárního stromu, který se běžně používá v informatice pro různé účely, včetně třídění, vyhledávání a organizování dat.

Úvod do Min-Heap – Struktura dat a výukové programy algoritmů

Účel a případy použití minimální haldy:

Implementace prioritní fronty: Jedním z primárních použití datové struktury haldy je implementace prioritních front.
Dijkstrův algoritmus : Dijkstrův algoritmus je algoritmus nejkratší cesty, který najde nejkratší cestu mezi dvěma uzly v grafu. Pro sledování nenavštívených uzlů s nejmenší vzdáleností od zdrojového uzlu lze použít minimální haldu.
řazení: Minimální haldu lze použít jako třídicí algoritmus k efektivnímu třídění kolekce prvků ve vzestupném pořadí.
Medián nálezu: K efektivnímu nalezení mediánu proudu čísel lze použít minimální hromadu. Můžeme použít jednu min hromadu pro uložení větší poloviny čísel a jednu max hromadu pro uložení menší poloviny. Medián bude kořenem minimální haldy.

Struktura dat Min-Heap v různých jazycích:

1. Min-Heap v C++

Minimální hromadu lze implementovat pomocí priorita_fronta kontejner z knihovny standardních šablon (STL). The priorita_fronta kontejner je typ adaptéru kontejneru, který poskytuje způsob ukládání prvků do datové struktury podobné frontě, ve které má každý prvek přiřazenou prioritu.

Syntax :

C++

 priority_queue < int, vector , větší > minH;>

2. Min-Heap v Javě

V Javě lze min haldu implementovat pomocí PriorityQueue třídy od balíček java.util . Třída PriorityQueue je prioritní fronta, která poskytuje způsob ukládání prvků do datové struktury podobné frontě, ve které má každý prvek přiřazenou prioritu.

Syntax :

Jáva

 PriorityQueue minHeap = nová fronta priority ();>

3. Min-Heap v Pythonu

V Pythonu lze min haldu implementovat pomocí heapq modul, který poskytuje funkce pro implementaci hald. Konkrétně heapq modul poskytuje způsob, jak vytvářet a manipulovat s datovými strukturami haldy.

Syntax:

Krajta

 heap = [] heapify(heap)>

4. Minimální halda v C#

V C# lze minimální haldu implementovat pomocí třídy PriorityQueue z System.Collections.Generic namespace . Třída PriorityQueue je prioritní fronta, která poskytuje způsob ukládání prvků do datové struktury podobné frontě, ve které má každý prvek přiřazenou prioritu.

odstranit poslední znak z řetězce

Syntax:

 var minHeap = new PriorityQueue ();>

5. Minimální halda v JavaScriptu

Min halda je binární strom, kde každý uzel má hodnotu menší nebo rovnou jeho potomkům. V JavaScriptu můžete implementovat minimální haldu pomocí pole, kde první prvek představuje kořenový uzel a potomci uzlu na indexu i se nacházejí na indexech 2i+1 a 2i+2.

Syntax:

JavaScript

 const minHeap = new MinHeap();>

Rozdíl mezi minimální haldou a maximální haldou:

	Min. halda	Max Heap
1.	V Min-Heap musí být klíč přítomný v kořenovém uzlu menší nebo roven mezi klíči přítomnými u všech jeho potomků.	V Max-Heap musí být klíč přítomný v kořenovém uzlu větší nebo roven mezi klíči přítomnými u všech jeho potomků.
2.	V Min-Heap je minimální klíčový prvek přítomen v kořenu.	V Max-Heap je maximální klíčový prvek přítomen v kořenovém adresáři.
3.	Min-Heap používá vzestupnou prioritu.	Max-Heap používá sestupnou prioritu.
4.	Při konstrukci min-hromady má přednost nejmenší prvek.	Při konstrukci Max-Heap má největší prvek přednost.
5.	V Min-Heap je nejmenší prvek první, který je vytažen z hromady. npm cache vymazat	V Max-Heap je největší prvek první, který je vytažen z hromady.

Interní implementace datové struktury Min-Heap:

A Minimální halda je obvykle reprezentována jako pole .

Kořenový prvek bude v Arr[0] .
Pro jakýkoli i-tý uzel Arr[i] :
Arr[(i -1) / 2] vrátí svůj nadřazený uzel.
Arr[(2 * i) + 1] vrátí svůj levý podřízený uzel.
Arr[(2 * i) + 2] vrátí svůj pravý podřízený uzel.

Interní implementace Min-Heap vyžaduje 3 hlavní kroky:

Vložení : Chcete-li vložit prvek do minimální haldy, nejprve jej připojíme na konec pole a poté upravíme vlastnost haldy opakovaným prohozením prvku s jeho rodičem, dokud nebude ve správné poloze.
Vymazání : Abychom odstranili minimální prvek z minimální hromady, nejprve zaměníme kořenový uzel s posledním prvkem v poli, odstraníme poslední prvek a poté upravíme vlastnost haldy opakovaným záměnou prvku s jeho nejmenším potomkem, dokud nebude v správná poloha.
Heapify : Operaci heapify lze použít k vytvoření minimální haldy z netříděného pole.

Operace s datovou strukturou minimální haldy a jejich implementace:

Zde jsou některé běžné operace, které lze provádět na datové struktuře haldy,

jak převést celé číslo na řetězec java

1. Vložení do datové struktury Min-Heap :

Prvky mohou být vkládány do hromady podobným postupem, jaký byl popsán výše pro mazání. Cílem je:

Operace vložení do min-hromady zahrnuje následující kroky:
Přidejte nový prvek na konec haldy na další dostupnou pozici v poslední úrovni stromu.
Porovnejte nový prvek s jeho nadřazeným prvkem. Pokud je nadřazený prvek větší než nový prvek, prohoďte je.
Opakujte krok 2, dokud nebude nadřazený prvek menší nebo roven novému prvku, nebo dokud nový prvek nedosáhne kořene stromu.
Nový prvek je nyní na své správné pozici v minimální haldě a vlastnost haldy je splněna.

Ilustrace:

Předpokládejme, že halda je minimální halda jako:

Vložení do Min-Hromy

Implementace operace vkládání v 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) { // Přidání nového prvku na konec haldy heap.push_back(value);  // Získání indexu posledního prvku int index = heap.size() - 1;  // Porovnejte nový prvek s jeho rodičem a // v případě potřeby swap while (index> 0 && heap[(index - 1) / 2]> heap[index]) { swap(heap[index], heap[(index - 1) / 2]);  // Přesune strom nahoru k rodiči aktuálního // prvku index = (index - 1) / 2;  } } // Hlavní funkce pro testování funkce insert_min_heap int main() { vector halda;  hodnoty int[] = { 10, 7, 11, 5, 4, 13 };  int n = sizeof(hodnoty) / sizeof(hodnoty[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; }>

Jáva

 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 && halda[(index - 1) / 2]> halda[index]) { swap(hromada, index, (index - 1) / 2);  // Přesune strom nahoru k rodiči aktuálního // prvku index = (index - 1) / 2;  } } // Funkce pro záměnu dvou prvků v poli public static void swap(int[] arr, int i, int j) { int temp = arr[i];  arr[i] = arr[j];  arr[j] = teplota;  } // Hlavní funkce pro testování funkce insertMinHeap public static void main(String[] args) { int[] heap = new int[6];  hodnoty int[] = { 10, 7, 11, 5, 4, 13 };  int velikost = 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 a halda[(index - 1) // 2]> halda[index]: halda[index], halda[(index - 1) // 2] = halda[(index - 1) // 2], halda[ index] # Přesunout strom nahoru na rodič aktuálního prvku index = (index - 1) // 2 halda = [] hodnoty = [10, 7, 11, 5, 4, 13] pro hodnotu v hodnotách: insert_min_heap( halda, hodnota) print(f'Vloženo {value} do min-hromady: {heap}')>

 using System; using System.Collections.Generic; public class Program {  // Function to insert a new element into the min-heap  static void InsertMinHeap(List halda, int hodnota) { // Přidání nového prvku na konec haldy.Add(value);  // Získání indexu posledního prvku int index = heap.Count - 1;  // Porovnejte nový prvek s jeho rodičem a v případě potřeby prohoďte // while (index> 0 && heap[(index - 1) / 2]> heap[index]) { int temp = heap[index];  halda[index] = halda[(index - 1) / 2];  halda[(index - 1) / 2] = teplota;  // Přesune strom nahoru k rodiči aktuálního // prvku index = (index - 1) / 2;  } } // Hlavní funkce pro testování funkce InsertMinHeap public static void Main() { List halda = nový Seznam ();  hodnoty int[] = { 10, 7, 11, 5, 4, 13 };  foreach(int hodnota v hodnotách) { InsertMinHeap(hromada, hodnota);  Console.Write('Vloženo ' + hodnota + ' do min-hromady: ');  foreach(prvek int v haldě) { 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 && halda[parentIndex]> halda[index]) { [hromada[index], halda[parentIndex]] = [hromada[parentIndex], halda[index]];  index = parentIndex;  parentIndex = Math.floor((index - 1) / 2);  } } // Příklad použití const heap = []; konstantní hodnoty = [10, 7, 11, 5, 4, 13]; for (konst. hodnota hodnot) { insertMinHeap(halda, hodnota);  console.log(`Vloženo ${value} do min-hromady: ${heap}`); }>

Výstup

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...>

Časová složitost: O(log(n)) ( kde n je číslo prvků v hromadě )
Pomocný prostor: Na)

2. Odstranění v datové struktuře Min-Heap :

Odstranění nejmenšího prvku (kořenu) z minimální haldy. Kořen je nahrazen posledním prvkem v haldě a poté je vlastnost haldy obnovena záměnou nového kořenového adresáře s jeho nejmenším potomkem, dokud není rodič menší než oba potomci nebo dokud nový kořen nedosáhne listového uzlu.

Nahraďte kořen nebo prvek, který chcete odstranit, posledním prvkem.
Odstraňte poslední prvek z haldy.
Protože poslední prvek je nyní umístěn na pozici kořenového uzlu. Nemusí tedy následovat vlastnost haldy. Proto navraťte poslední uzel umístěný na pozici kořene.

Ilustrace :

Předpokládejme, že halda je minimální halda jako:

Struktura dat min-haldy

Prvek, který má být odstraněn, je root, tedy 13.

Proces :

Poslední prvek je 100.

Krok 1: Nahraďte poslední prvek rootem a odstraňte jej.

Struktura dat min-haldy

Krok 2 : Heapify root.

Konečná hromada:

Struktura dat min-haldy

Implementace operace mazání v 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) { // Přidání nového prvku na konec haldy heap.push_back(value);  // Získání indexu posledního prvku int index = heap.size() - 1;  // Porovnejte nový prvek s jeho rodičem a // v případě potřeby swap while (index> 0 && heap[(index - 1) / 2]> heap[index]) { swap(heap[index], heap[(index - 1) / 2]);  // Přesune strom nahoru k rodiči aktuálního // prvku index = (index - 1) / 2;  } } // Funkce pro odstranění uzlu z min-heap void delete_min_heap(vector & halda, int hodnota) { // Nalezení indexu prvku, který má být smazán 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 halda;  hodnoty int[] = { 13, 16, 31, 41, 51, 100 };  int n = sizeof(hodnoty) / sizeof(hodnoty[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; }>

Jáva

 import java.util.*; public class GFG {  // Function to insert a new element into the min-heap  public static void insertMinHeap(List heap, int value) { // Přidání nového prvku na konec haldy heap.add(value);  // Získání indexu posledního prvku int index = heap.size() - 1;  // Porovnejte nový prvek s jeho rodičem a // v případě potřeby zaměňte while (index> 0 && heap.get((index - 1) / 2)> heap.get(index)) { Collections.swap(heap, index, (index - 1) / 2);  // Přesune strom nahoru k rodiči aktuálního // prvku index = (index - 1) / 2;  } } // Funkce pro odstranění uzlu z min-heap public static void deleteMinHeap(List halda, int hodnota) { // Nalezení indexu prvku, který má být smazán 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 halda = nový ArrayList ();  hodnoty int[] = { 13, 16, 31, 41, 51, 100 };  int n = hodnoty.délka;  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 a halda[(index - 1) // 2]> halda[index]: halda[index], halda[(index - 1) // 2] = halda[(index - 1) // 2], halda[ index] index = (index - 1) // 2 def delete_min_heap(heap, value): index = -1 for i in range(len(heap)): if heap[i] == value: index = i break if index == -1: návrat heap[index] = heap[-1] heap.pop() while True: left_child = 2 * index + 1 right_child = 2 * index + 2 nejmenší = index, pokud 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)>

 using System; using System.Collections.Generic; class MinHeap {  private List halda = nový Seznam ();  public void Insert(int value) { heap.Add(value);  int index = halda.Pocet - 1;  while (index> 0 && halda[(index - 1) / 2]> halda[index]) { Swap(index, (index - 1) / 2);  index = (index - 1) / 2;  } } public void Smazat(int hodnota) { int index = halda.IndexOf(hodnota);  if (index == -1) { return;  } halda[index] = halda[hromada.Pocet - 1];  heap.RemoveAt(heap.Count - 1);  while (true) { int leftChild = 2 * index + 1;  int rightChild = 2 * index + 2;  int nejmenší = index;  if (leftChild< 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 && heap[flr]> heap[index]; flr = Math.floor((index - 1) / 2)) { [hromada[index], halda[flr]] = [ halda[flr], halda[index], ];  // Přesune strom nahoru k rodiči aktuálního prvku index = Math.floor((index - 1) / 2);  } } function deleteMinHeap(heap, value) { // Najděte index prvku, který se má smazat nechť index = -1;  for (ať 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(' '));>

Výstup

Initial heap: 13 16 31 41 51 100 Heap after deleting 13: 16 41 31 100 51>

Časová složitost : O(log n) kde n je číslo prvků v haldě
Pomocný prostor: Na)

3. Operace náhledu na datové struktuře Min-Heap:

Pro přístup k minimálnímu prvku (tj. kořenu haldy) je vrácena hodnota kořenového uzlu. Časová složitost náhledu v min-hromadě je O(1).

Minimální datová struktura haldy

Implementace operace Peek v Min-Heap:

C++

 #include  #include  #include  using namespace std; int main() {  // Create a max heap with some elements using a  // priority_queue  priority_queue , větší > 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);  // Získání vrcholového prvku (tj. největšího prvku) int peakElement = minHeap.top();  // Vytiskne vrchol prvku cout<< 'Peak element: ' << peakElement << std::endl;  return 0; }>

Jáva

 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);  // Získání vrcholového prvku (tj. největšího prvku) int peakElement = minHeap.peek();  // Vytiskne prvek vrcholu System.out.println('Prvek vrcholu: ' + 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)>

 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);  // Získání vrcholového prvku (tj. nejmenšího prvku) int peakElement = minHeap.Peek();  // Tisk prvku vrcholu Console.WriteLine('Prvek vrcholu: ' + 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); // Získání vrcholového prvku (tj. nejmenšího prvku) const peakElement = minHeap.peek(); // Vytiskne prvek vrcholu console.log(`Prvek vrcholu: ${peakElement}`);>

Výstup

Peak element: 1>

Časová složitost : V minimální haldě implementované pomocí pole nebo seznamu lze k prvku peak přistupovat v konstantním čase, O(1), protože je vždy umístěn v kořenu haldy.
V minimální haldě implementované pomocí binárního stromu lze k prvku peak přistupovat také v čase O(1), protože je vždy umístěn v kořeni stromu.

Pomocný prostor: Na)

4. Operace heapify na datové struktuře Min-Heap:

Operaci heapify lze použít k vytvoření minimální haldy z netříděného pole. To se provádí tak, že se začne od posledního nelistového uzlu a opakovaně se provádí operace bublina dolů, dokud všechny uzly nesplní vlastnost haldy.

Operace Heapify v Min Heap

Implementace operace Heapify v Min-Heap:

C++

 #include  #include  using namespace std; void minHeapify(vector &arr, int i, int n) { int nejmenší = i;  int 1 = 2*i + 1;  int r = 2*i + 2;  pokud (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; }>

Jáva

 // 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) { // Předpokládejme, že kořen je nejmenší prvek zpočátku int nejmenší = i;  // Vypočítejte indexy levého a pravého potomka aktuálního uzlu int l = 2 * i + 1;  int r = 2 * i + 2;  // Porovnejte levé dítě s aktuálním nejmenším if (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('Původní pole: ');  // Vytiskne původní pole pro (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 po operaci heapify: ');  // Vytiskne min-hromadu po operaci heapify pro (int i = 0; i< arr.size(); i++)  System.out.print(arr.get(i) + ' ');  } }>

Krajta

 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)>

 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 nejmenší = i;  int vlevo = 2 * i + 1;  int vpravo = 2 * i + 2;  // Porovnejte levé dítě s aktuálním nejmenším uzlem.  pokud (vlevo< 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 = nový seznam { 10, 5, 15, 2, 20, 30};  Console.Write('Původní pole: ');  foreach (int num v arr) Console.Write(num + ' ');  // Proveďte operaci heapify na min-haldě.  for (int i = arr.Count / 2 - 1; i>= 0; i--) MinHeapify(arr, i, arr.Count);  Console.Write('
Min-Heap po operaci heapify: ');  foreach (int num v 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.length);  // Tisk min-hromady po operaci heapify console.log('Min-Heap po operaci heapify: ' + arr.join(' ')); } // Volání funkce main pro spuštění procesu main();>

Výstup

Original array: 10 5 15 2 20 30 Min-Heap after heapify operation: 2 5 15 10 20 30>

Časová složitost heapify v min-hromadě je O(n).

5. Operace vyhledávání na datové struktuře Min-Heap:

Chcete-li vyhledat prvek v minimální hromadě, lze provést lineární vyhledávání přes pole, které představuje hromadu. Časová složitost lineárního vyhledávání je však O(n), což není efektivní. Hledání proto není běžně používaná operace v min hromadě.

Zde je příklad kódu, který ukazuje, jak hledat prvek v minimální hromadě pomocí std::najít() :

Hru holub pro android

C++

 #include  using namespace std; int main() {  priority_queue , větší > min_hromada;  // příklad max haldy min_heap.push(10);  min_heap.push(9);  min_heap.push(8);  min_heap.push(6);  min_heap.push(4);  prvek int = 6; // prvek pro hledání bool nalezen = false;  // Zkopírujte minimální hromadu do dočasné fronty a vyhledejte // prvek std::priority_queue , větší > teplota = min_hromada;  while (!temp.empty()) { if (temp.top() == element) { found = true;  přestávka;  } temp.pop();  } if (nalezeno) { std::cout<< 'Element found in the min heap.'  << std::endl;  }  else {  std::cout << 'Element not found in the min heap.'  << std::endl;  }  return 0; }>

Jáva

 import java.util.PriorityQueue; public class GFG {  public static void main(String[] args)  {  PriorityQueue min_heap = new PriorityQueue();  min_heap.add( 3); // vložení prvků do prioritní fronty min_heap.offer(1);  min_hromada.nabídka(4);  min_hromada.nabídka(1);  min_hromada.nabídka(6);  prvek int = 6; // nalezený prvek pro hledání boolean = false;  // Zkopírujte minimální hromadu do dočasné fronty a vyhledejte // prvek PriorityQueue temp = new PriorityQueue(min_heap);  while (!temp.isEmpty()) { if (temp.poll() == element) { found = true;  přestávka;  } } if (nalezeno) { System.out.println( 'Prvek nalezen v min. hromadě.');  } else { System.out.println( 'Prvek nebyl nalezen v min. hromadě.');  } } }>

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.')>

 using System; using System.Collections.Generic; public class GFG {  public static void Main()  {  var minHeap = new PriorityQueue ();  // příklad min haldy minHeap.Enqueue(4);  minHeap.Enqueue(6);  minHeap.Enqueue(8);  minHeap.Enqueue(9);  minHeap.Enqueue(10);  prvek int = 6; // prvek pro hledání bool nalezen = false;  // Zkopírujte minimální hromadu do dočasné fronty a vyhledejte // prvek var temp = new PriorityQueue (minHeap);  while (temp.Count> 0) { if (temp.Peek() == element) { found = true;  přestávka;  } temp.Dequeue();  } if (nalezeno) { Console.WriteLine( 'Prvek nalezen v min. hromadě.');  } else { Console.WriteLine( 'Prvek nebyl nalezen v min. hromadě.');  } } }>

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;  přestávka;  } temp.dequeue(); } if (found) { console.log('Prvek nalezen v min. hromadě.'); } else { console.log('Prvek nebyl nalezen v hromadě min.'); }>

Výstup

Element found in the min heap.>

Analýza složitosti :

The časovou složitost tohoto programu je O(n log n) , kde n je počet prvků v prioritní frontě.

Operace vkládání má časovou složitost O(log n) v nejhorším případě, protože je třeba udržovat vlastnost haldy. Operace vyhledávání zahrnuje zkopírování prioritní fronty do dočasné fronty a následné procházení dočasné fronty, což trvá O(n log n) čas v nejhorším případě, protože každý prvek je třeba zkopírovat a vybrat z fronty a prioritní frontu je třeba pro každou operaci znovu sestavit.

The prostorová složitost programu je Na) protože ukládá n prvků ve frontě priority a vytvoří dočasnou frontu s n Prvky.

Aplikace datové struktury Min-Heap:

Řazení haldy: Min halda se používá jako klíčová součást v algoritmu řazení haldy, což je účinný třídicí algoritmus s časovou složitostí O(nlogn).
Prioritní fronta: Prioritní frontu lze implementovat pomocí datové struktury min haldy, kde je prvek s minimální hodnotou vždy v kořenu.
Dijkstrův algoritmus: V Dijkstrově algoritmu se používá min halda k uložení vrcholů grafu s minimální vzdáleností od počátečního vrcholu. Vrchol s minimální vzdáleností je vždy u kořene haldy.
Huffmanovo kódování: V Huffmanově kódování se minimální hromada používá k implementaci prioritní fronty k vytvoření optimálního předponového kódu pro danou sadu znaků.
Sloučit K seřazená pole: Vzhledem k K seřazeným polím je můžeme efektivně sloučit do jediného setříděného pole pomocí minimální haldy datové struktury.

Výhody datové struktury s minimální haldou:

Efektivní vkládání a mazání : Min halda umožňuje rychlé vkládání a mazání prvků s časovou složitostí O(log n), kde n je počet prvků v haldě.
Efektivní načtení minimálního prvku: Minimální prvek v minimální hromadě je vždy v kořenu hromady, který lze získat v čase O(1).
Prostorově úsporné: Min halda je kompaktní datová struktura, kterou lze implementovat pomocí pole nebo binárního stromu, díky čemuž je prostorově efektivní.
řazení: Min haldy lze použít k implementaci efektivního třídícího algoritmu, jako je haldové řazení s časovou složitostí O(n log n).
Prioritní fronta: Minimální haldu lze použít k implementaci prioritní fronty, kde lze prvek s minimální prioritou efektivně načíst v čase O(1).
Všestrannost: Min heap má několik aplikací v počítačové vědě, včetně grafových algoritmů, komprese dat a databázových systémů.

Celkově je min halda užitečná a všestranná datová struktura, která nabízí efektivní operace, prostorovou efektivitu a má několik aplikací v počítačové vědě.