Montículo binario
| Montículo binario | |||||||||
|---|---|---|---|---|---|---|---|---|---|
| |||||||||
| |||||||||
| |||||||||
| Wikidata C:Commons | |||||||||


Un montículo binario é un montículo que toma a forma dunha árbore binaria. Os montículos binarios son unha forma común de implementar colas de prioridade.[1]:pp. 162–163 O montículo binario foi introducido por J. W. J. Williams en 1964 como estrutura de datos para o heapsort.[2]
Un montículo binario defínese como unha árbore binaria con dúas restricións adicionais:[3]
- Propiedade de forma: un montículo binario é unha árbore binaria completa; isto é, todos os niveis da árbore, agás quizais o último (o máis profundo), están completamente cheos e, se o último nivel non está cheo, os seus nós énchense de esquerda a dereita.
- Propiedade do montículo: a chave almacenada en cada nó é maior ou igual (≥) (ou menor ou igual (≤)) que as chaves dos fillos do nó, segundo unha orde total.
Os montículos nos que a chave do pai é maior ou igual (≥) cá dos fillos chámanse montículos máximo; aqueles nos que é menor ou igual (≤) chámanse montículos mínimo. Coñécense algoritmos eficientes (isto é, de tempo logarítmico) para as dúas operacións necesarias para implementar unha cola de prioridade nun montículo binario:
- Inserir un elemento.
- Eliminar o elemento menor ou maior dun montículo mínimo ou máximo, respectivamente.
Os montículos binarios tamén se empregan habitualmente no algoritmo de ordenación heapsort, que é un algoritmo in situ, pois os montículos binarios poden implementarse como estrutura de datos implícita, almacenando as chaves nun vector e usando as súas posicións relativas para representar as relacións fillo-pai.
Operacións do montículo
[editar | editar a fonte]Tanto a inserción como o borrado modifican o montículo para conservar primeiro a propiedade de forma, engadindo ou retirando ao final do montículo. Despois restablécese a propiedade do montículo percorréndoo cara arriba ou cara abaixo. Ambas as operacións levan tempo O(log n).
Inserción
[editar | editar a fonte]Para inserir un elemento nun montículo:
- Engadir o elemento ao nivel inferior, no primeiro oco libre pola esquerda.
- Comparar o elemento engadido co seu pai; se están na orde correcta, parar.
- Se non, intercambiar o elemento co seu pai e volver ao paso anterior.
Os pasos 2 e 3, que restauran a propiedade do montículo comparando e intercambiando un nó co seu pai, chámanse operación up-heap (tamén bubble-up, percolate-up, sift-up, trickle-up, swim-up, heapify-up, cascade-up ou fix-up).
O número de operacións depende só do número de niveis que o novo elemento debe subir. Así, a inserción ten complexidade no peor caso O(log n). Para un montículo aleatorio e para insercións repetidas, a complexidade de media é O(1).[4][5]

A animación seguinte amosa un exemplo de inserción nun montículo binario. Comeza inserindo 15 no primeiro oco libre da seguinte fila. Como 15 > 8, a propiedade do montículo viólase, polo que se intercambian 15 e 8. Mesmo após este intercambio, a propiedade aínda se viola porque 15 > 11, polo que se intercambian de novo. Unha vez satisfeita a propiedade, a árbore resultante é un montículo máximo válido. Non cómpre comprobar o fillo esquerdo tras este paso final: ao comezo o montículo máximo era válido, así que a raíz xa era maior có seu fillo esquerdo, e substituír a raíz por un valor aínda maior mantén a propiedade.
Extracción
[editar | editar a fonte]O procedemento para borrar a raíz do montículo (extraendo o máximo nun montículo máximo ou o mínimo nun mínimo) conservando a propiedade é o seguinte:
- Substituír a raíz do montículo polo último elemento do último nivel.
- Comparar a nova raíz cos seus fillos; se están na orde correcta, parar.
- Se non, intercambiar o elemento cun dos fillos e volver ao paso anterior. (Co fillo menor nun montículo mínimo e co maior nun máximo.)
Os pasos 2 e 3 chámanse operación down-heap (tamén bubble-down, percolate-down, sift-down, sink-down, trickle down, heapify-down, cascade-down, fix-down, extract-min ou extract-max, ou simplemente heapify).

O nó que baixa intercámbiase co maior dos seus fillos nun montículo máximo (co menor nun mínimo) ata satisfacer a propiedade na súa nova posición. Isto realízao a función Max-Heapify, definida en pseudocódigo para un montículo A indexado desde 1:
// Realizar unha operación down-heap para un montículo máximo
// A: vector que representa o montículo, indexado desde 1
// i: índice no que comezar a criba cara abaixo
Max-Heapify(A, i):
left ← 2×i
right ← 2×i + 1
largest ← i
if left ≤ length(A) and A[left] > A[largest] then:
largest ← left
if right ≤ length(A) and A[right] > A[largest] then:
largest ← right
if largest ≠ i then:
swap A[i] and A[largest]
Max-Heapify(A, largest)
Para aplicar Max-Heapify(A,i), as dúas subárbores fillas de i xa deben ser montículos válidos; a única posible violación dentro da subárbore está entre i e os seus fillos. A función restaura a propiedade nesa subárbore. Tamén se pode empregar tras modificar a raíz dun montículo.
No peor caso, a nova raíz hai que intercambiala co fillo en cada nivel ata o fondo, polo que o borrado ten complexidade O(log n).
Inserir e despois extraer
[editar | editar a fonte]Inserir un elemento e despois extraer pódese facer de forma máis eficiente ca chamar por separado ás funcións insert e extract, que implicarían unha operación upheap e outra downheap. No canto diso, pódese facer só unha operación downheap:
- Comparar se o elemento que se introduce é maior ca o da cima do montículo (supoñendo un montículo máximo).
- Se a raíz do montículo é maior:
- Substituír a raíz polo novo elemento.
- Facer down-heapify desde a raíz.
- Se non, devolver o elemento que se introduce.
Python ofrece heappushpop para montículos mínimos indexados desde 0.[6][7] O pseudocódigo seguinte ilustra a operación simétrica nun montículo máximo indexado desde 1.
// Introducir un novo elemento nun montículo (máximo) e extraer despois a raíz.
// heap: vector que representa o montículo, indexado desde 1
// item: elemento a inserir
Push-Pop(heap: List<T>, item: T) -> T:
if heap is not empty and heap[1] > item then: // < se é montículo mínimo
swap heap[1] and item
_downheap(heap starting from index 1)
return item
Unha función similar pódese definir para extraer e despois inserir, chamada en Python heapreplace:
// Extraer a raíz do montículo e introducir un novo elemento
// heap: vector que representa o montículo, indexado desde 1
// item: elemento a inserir
Replace(heap: List<T>, item: T) -> T:
swap heap[1] and item
_downheap(heap starting from index 1)
return item
Busca
[editar | editar a fonte]Atopar un elemento arbitrario leva tempo O(n), porque o montículo non está ordenado e hai que percorrer toda a árbore para atopar o elemento obxectivo.
Borrado
[editar | editar a fonte]Borrar un elemento arbitrario faise así:
- Atopar o índice do elemento que se quere borrar.
- Intercambialo co último elemento. Eliminar o último tras o intercambio.
- Facer down-heapify ou up-heapify para restablecer a propiedade. Nun montículo máximo (mínimo), só se require up-heapify cando a nova chave do elemento é maior (menor) ca a anterior. Cando a nova chave é menor (maior) ca a anterior, só se require down-heapify.
Diminución ou aumento de chave
[editar | editar a fonte]A operación de diminución de chave substitúe o valor dun nó por un valor menor, e a de aumento fai o mesmo cun valor maior. Implica atopar o nó, cambiar o valor e despois facer down-heapify ou up-heapify.
A diminución de chave faise así:
- Atopar o índice do elemento que se quere modificar.
- Diminuír o valor do nó.
- Facer down-heapify (supoñendo un montículo máximo).
O aumento de chave faise así:
- Atopar o índice do elemento que se quere modificar.
- Aumentar o valor do nó.
- Facer up-heapify (supoñendo un montículo máximo).
Construción dun montículo (Heapify)
[editar | editar a fonte]Construír un montículo a partir dun vector de elementos pódese facer partindo dun montículo baleiro e inserindo cada elemento sucesivamente. Equivalentemente, pódese colocar os elementos arbitrariamente na árbore e despois facer up-heapify de cada nó, o que permite a construción in situ. Este método, chamado método de Williams, corre en .[nb 1]
No entanto, o método de Williams é subóptimo no peor caso. Un método máis rápido, debido a Floyd,[8] comeza colocando arbitrariamente os elementos nunha árbore binaria respectando a propiedade de forma. Despois, partindo do nivel máis baixo e subindo, criba a raíz de cada subárbore cara abaixo ata restablecer a propiedade. Se todas as subárbores a partir dunha altura xa están amontoadas (o nivel máis baixo corresponde a ), pódense amontoar as de altura enviando a súa raíz cara abaixo polo camiño dos fillos de máximo valor (mínimo valor para un montículo mínimo). Este proceso leva operacións por nó. Como a maior parte da amontoación ocorre nos niveis baixos, o custo total é:
Isto usa o feito de que a serie infinita converxe.
O valor exacto do número de comparacións no peor caso durante a construción é:
onde é a suma dos díxitos da representación binaria de e é o expoñente de 2 na factorización de .
O caso medio é máis complexo de analizar, pero pódese amosar que se aproxima asintoticamente a comparacións.[10][11]
A función Build-Max-Heap converte un vector A que almacena unha árbore binaria completa de n nós nun montículo máximo, usando repetidamente Max-Heapify de abaixo arriba. Os elementos cos índices son follas, e non cómpre crialos:
Build-Max-Heap (A):
for each index i from floor(length(A)/2) downto 1 do:
Max-Heapify(A, i)
Implementación do montículo
[editar | editar a fonte]
Os montículos adoitan implementarse cun vector. Calquera árbore binaria se pode almacenar nun vector, pero como un montículo binario é sempre unha árbore binaria completa, pódese almacenar de forma compacta. Non se necesita espazo para punteiros; o pai e os fillos de cada nó atópanse por aritmética de índices. Isto fai que esta implementación sexa un exemplo sinxelo de estrutura de datos implícita. Os detalles dependen da posición da raíz.
Sexa o número de elementos do montículo e un índice válido. Se a raíz está no índice 0 (índices válidos de 0 a ), cada elemento no índice ten:
- fillos nos índices e ;
- o seu pai no índice .
Alternativamente, se a raíz está no índice 1 (índices de 1 a ), cada elemento no índice ten:
- fillos nos índices e ;
- o seu pai no índice .
Esta implementación úsase no heapsort, que reutiliza o espazo do vector de entrada para almacenar o montículo (é dicir, faise in situ). Tamén é útil como cola de prioridade. Cando se usa un vector dinámico, é posible inserir un número ilimitado de elementos.
As operacións upheap e downheap pódense expresar en termos do vector. A función sift-down avanza polo fillo correspondente e pode escribirse de forma recursiva de cola ou iterativa. Nun montículo de elementos require como máximo descensos, con ata dúas comparacións de chaves por nivel.
Para montículos grandes con memoria virtual, almacenar os elementos nun vector como se indicou é ineficiente, porque case todos os niveis están en páxinas distintas. Os B-heaps son montículos binarios que manteñen as subárbores nunha soa páxina, reducindo o número de páxinas accedidas.[12]
A fusión de dous montículos binarios leva Θ(n) para montículos do mesmo tamaño; a mellor opción é concatenar os dous vectores e construír un montículo co resultado.[13] Cando a fusión é unha tarefa común, recoméndase outra implementación de montículo, como os montículos binomials, que se poden fusionar en O(log n).
Ademais, un montículo binario pódese implementar cunha estrutura de árbore binaria tradicional, pero xorde un problema ao atopar o elemento adxacente no último nivel ao engadir un elemento. Este elemento pódese determinar algorítmicamente ou engadindo datos extra aos nós (o chamado «encadeado» da árbore).
É posible modificar a estrutura do montículo para facer a extracción tanto do menor como do maior elemento en tempo .[14] Para iso, as filas alternan entre montículo mínimo e máximo. A idea pódese xeneralizar a un montículo mínimo-máximo-mediana.
Derivación das ecuacións de índice
[editar | editar a fonte]Nun montículo baseado en vector, os fillos e o pai dun nó pódense localizar mediante aritmética simple sobre o índice do nó. Nesta sección derívanse as ecuacións para montículos coa raíz no índice 0.
Para evitar confusión, defínese o nivel dun nó como a súa distancia á raíz, de xeito que a propia raíz ocupa o nivel 0.
Nós fillos
[editar | editar a fonte]Para un nó xeral no índice (comezando en 0), primeiro derívase o índice que ocuparía o seu fillo dereito, , se existe. Nunha árbore binaria perfecta de referencia, cada nivel contén exactamente nós, e hai nós ata ese nivel inclusive. Nun montículo completo, só o último nivel pode estar incompleto; os índices dos nós presentes coinciden cos desta árbore de referencia. Como a raíz está en 0, o -ésimo nó gárdase no índice . O índice da posición final do nivel na árbore de referencia é:
Sexa o número de posicións despois do nó no nivel da árbore perfecta de referencia, de xeito que . Nesa árbore, cada unha desas posicións ten dous fillos, polo que hai posicións entre o fillo dereito de e o final do nivel . Entón:
Como o fillo esquerdo sempre está unha posición antes cá do dereito, tense . Se a raíz está no índice 1, entón e .
Nó pai
[editar | editar a fonte]Todo nó non raíz é fillo esquerdo ou dereito do seu pai, polo que se cumpre unha das dúas:
Polo tanto, ou . Considerando : se o nó é fillo esquerdo, dá o resultado inmediatamente; se é fillo dereito, é par e é impar, e tense
Polo tanto, independentemente de se o nó é fillo esquerdo ou dereito, o seu pai atópase con .
Estruturas relacionadas
[editar | editar a fonte]Como a ordenación dos irmáns nun montículo non está especificada pola propiedade do montículo, os dous fillos dun nó pódense intercambiar libremente, sempre que iso non viole a propiedade de forma (compárese co treap). Con todo, no montículo común baseado en vector, intercambiar os fillos pode requirir mover as subárbores para conservar a propiedade.
O montículo binario é un caso particular do montículo d-ario con .
Notas
[editar | editar a fonte]- ↑ De feito, este procedemento pódese amosar que leva no peor caso. No caso medio, con todo, o método leva tempo linear.
- ↑ Isto non significa que a ordenación se poida facer en tempo linear, xa que construír un montículo só é o primeiro paso do heapsort.
- ↑ Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2009). Introduction to Algorithms (en inglés) (3.ª ed.). MIT Press. ISBN 978-0-262-03384-8.
- ↑ Williams, J. W. J. (1964). "Algorithm 232 - Heapsort". Communications of the ACM (en inglés) 7 (6): 347–348. doi:10.1145/512274.3734138.
- ↑ Narahari, Y. "Binary Heaps". Data Structures and Algorithms (en inglés).
- ↑ Porter, Thomas; Simon, Istvan (setembro de 1975). "Random insertion into a priority queue structure". IEEE Transactions on Software Engineering (en inglés) SE–1 (3): 292–298. ISSN 1939-3520. doi:10.1109/TSE.1975.6312854.
- ↑ Mehlhorn, Kurt; Tsakalidis, A. (febreiro de 1989). "Data structures" (en inglés). Universität des Saarlandes: 27. doi:10.22028/D291-26123. Arquivado dende o orixinal o 29 de agosto de 2024. Consultado o 20 de setembro de 2026.
- ↑ "python/cpython/heapq.py". GitHub (en inglés).
- ↑ "heapq — Heap queue algorithm — Python 3.8.5 documentation". docs.python.org (en inglés).
- ↑ Floyd, Robert W. (1964). "Algorithm 245: Treesort". Communications of the ACM (en inglés) 7 (12): 701. doi:10.1145/355588.365103.
- ↑ Suchenek, Marek A. (2012). "Elementary Yet Precise Worst-Case Analysis of Floyd's Heap-Construction Program". Fundamenta Informaticae (en inglés) 120 (1): 75–92. doi:10.3233/FI-2012-751..
- ↑ Doberkat, Ernst E. (maio de 1984). "An Average Case Analysis of Floyd's Algorithm to Construct Heaps" (PDF). Information and Control (en inglés) 61 (2): 114–131. doi:10.1016/S0019-9958(84)80053-4.
- ↑ Pasanen, Tomi (novembro de 1996). Elementary Average Case Analysis of Floyd's Algorithm to Construct Heaps (Informe técnico) (en inglés). Turku Centre for Computer Science. ISBN 951-650-888-X. TUCS Technical Report No. 64.
- ↑ Kamp, Poul-Henning (11 de xuño de 2010). "You're Doing It Wrong". ACM Queue (en inglés) 8 (6).
- ↑ Chris L. Kuszmaul. «binary heap». Dictionary of Algorithms and Data Structures, Paul E. Black (ed.), U.S. National Institute of Standards and Technology. 16 de novembro de 2009.
- ↑ Atkinson, M. D.; Sack, J.-R.; Santoro, N.; Strothotte, T. (1 de outubro de 1986). "Min-max heaps and generalized priority queues" (PDF) (en inglés). Programming techniques and Data structures. Comm. ACM, 29(10): 996–1000. Arquivado dende o orixinal (PDF) o 27 de xaneiro de 2007. Consultado o 20 de setembro de 2026.
Véxase tamén
[editar | editar a fonte]Outros artigos
[editar | editar a fonte]Ligazóns externas
[editar | editar a fonte]- Open Data Structures - Section 10.1 - BinaryHeap: An Implicit Binary Tree, Pat Morin (en inglés)
- Implementación dun montículo máximo binario en C, por Robin Thomas (en inglés)
- Implementación dun montículo mínimo binario en C, por Robin Thomas (en inglés)