A Munt és una estructura de dades d'arbre binari completa que compleix la propietat heap: per a cada node, el valor dels seus fills és menor o igual al seu propi valor. Els munts s'utilitzen normalment per implementar cues de prioritat, on l'element més petit (o més gran) sempre es troba a l'arrel de l'arbre.

Estructura de dades heap

Taula de contingut

• Tipus de munts
• Operacions Heap
• Què és Heap Data Structure?

  A Munt és una estructura de dades basada en un arbre binari que satisfà la propietat de l'emmagatzematge dinàmic: el valor de cada node és superior o igual al valor dels seus fills. Aquesta propietat assegura que el node arrel contingui el fitxer màxim o mínim valor (segons el tipus de pila) i els valors disminueixen o augmenten a mesura que us moveu per l'arbre.

  ls comanda linux

  Tipus de munts

  Hi ha dos tipus principals de munts:

  
  
  
  
  • Heap màxim: El node arrel conté el valor màxim, i els valors disminueixen a mesura que us moveu per l'arbre.
  • Min Heap: El node arrel conté el valor mínim i els valors augmenten a mesura que us moveu per l'arbre.

  Operacions Heap

  Les operacions comunes d'heap són:

  • Insereix : Afegeix un nou element a l'emmagatzematge dinàmic mentre es manté la propietat del munt.
  • Extracte màxim/mínim: Elimina l'element màxim o mínim de la pila i el retorna.
  • Heapify : converteix un arbre binari arbitrari en un munt.

  Els munts s'utilitzen habitualment per implementar cues de prioritat, on els elements es recuperen en funció de la seva prioritat (valor màxim o mínim).

• Heapsort és un algorisme d'ordenació que utilitza un munt per ordenar una matriu en ordre ascendent o descendent.
• Els munts s'utilitzen en algorismes de gràfics com algorisme de Dijkstra i algorisme de Prim per trobar els camins més curts i els arbres mínims.

Munt binari

Aplicacions, avantatges i desavantatges de Heap

Temps Complexitat de construir un munt

Comparació entre Heap i Tree

Quan es construeix un Heap, és única l'estructura del Heap?

Munt de Fibonacci

Heap d'esquerres

Munt K-ary

Ordenació de pila

Comproveu si un arbre binari donat és Heap

Com comprovar si una matriu donada representa un munt binari?

Ordenació de pila iterativa

K'è element més gran d'una matriu

K’th element més petit/més gran de la matriu no ordenada | Set 1

Alçada d'un arbre binari complet (o Heap) amb N nodes

Heap Ordena per ordre decreixent utilitzant min Heap

Imprimeix tots els nodes inferiors a un valor x en un munt mínim.

Arbre del torneig (arbre guanyador) i munt binari

Connecteu n cordes amb un cost mínim

Màxim d'elements diferents després d'eliminar k elements

K combinacions de suma màxima de dues matrius

Mediana del flux d'enters en execució mitjançant STL

Mediana en un flux d'enters (ners en curs)

K’è element més gran d’un corrent

El producte triplet més gran d'un corrent

Trobeu k nombres amb la majoria d'ocurrències a la matriu donada

Converteix min Heap en Heap màxim

Donat el recorregut per ordre de nivell d'un arbre binari, comproveu si l'arbre és un munt mínim

Combina k matrius ordenades | Set 1

Ordena els números emmagatzemats en diferents màquines

Mínima alteració de la seqüència

Major alteració d'una seqüència

Diferència màxima entre dos subconjunts de m elements

Convertir BST a Min Heap

Combina dos munts màxims binaris

K-th Suma més gran Subbarray contigu

Producte mínim de k nombres enters en una matriu de nombres enters positius

Reorganitza els caràcters d'una cadena de manera que no hi hagi dos adjacents iguals

Suma de tots els elements entre k1’è i k2’è elements més petits

Suma mínima de dos nombres formats a partir de dígits d'una matriu

Links ràpids:

• Problemes de pràctica en Heap
• Recomanat:
  • Apreneu l'estructura de dades i els algorismes | Tutorial DSA