miniatura|dereita|alt=Exemplo dun montículo máximo binario completo.|Exemplo dun montículo máximo binario completo. miniatura|alt=Exemplo dun montículo mínimo binario completo.|Exemplo dun montículo mínimo binario completo.
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. O montículo binario foi introducido por J. W. J. Williams en 1964 como estrutura de datos para o heapsort.
Un montículo binario defínese como unha árbore binaria con dúas restricións adicionais: 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 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 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). miniatura|299x299px|alt=Animación da inserción dun valor nun montículo máximo binario.|Animación breve que amosa a inserción dun valor nun montículo máximo binario. 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 , 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 , 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 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). miniatura|300x300px|alt=Animación da extracción dun valor dun montículo máximo binario.|Animación breve que amosa a extracción dun valor dun montículo máximo binario.
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 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. 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 > item then: // < se é montículo mínimo swap heap 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 and item _downheap(heap starting from index 1) return item
Busca 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 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 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) 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 .De feito, este procedemento pódese amosar que leva no peor caso. No caso medio, con todo, o método leva tempo linear.
No entanto, o método de Williams é subóptimo no peor caso. Un método máis rápido, debido a Floyd, 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 é: ,.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. 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.
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 dereita|frame|alt=Árbore binaria completa pequena almacenada nun vector.|Unha pequena árbore binaria completa almacenada nun vector.
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.