miniatura|alt=Exemplo dun montículo máximo binario con chaves enteiras entre 1 e 100.|Exemplo dun montículo máximo binario con chaves enteiras entre 1 e 100.
En ciencias da computación, un montículo é unha estrutura de datos en forma de árbore que satisfai a propiedade do montículo: nun montículo máximo, para calquera nó C, se P é o nó pai de C, entón a chave (o valor) de P é maior ou igual que a de C. Nun montículo mínimo, a chave de P é menor ou igual que a de C.Black (ed.), Paul E. (14 de decembro de 2004). Entrada «heap» en Dictionary of Algorithms and Data Structures. U.S. National Institute of Standards and Technology. O nó na «cima» do montículo (sen pai) chámase nó raíz.
O montículo é unha das implementacións máis eficientes dun tipo de dato abstracto chamado cola de prioridade; de feito, as colas de prioridade adoitan chamarse «montículos», independentemente de como se implementen. Nun montículo, o elemento de maior (ou menor) prioridade está sempre na raíz. Porén, un montículo non é unha estrutura ordenada: pódese considerar parcialmente ordenado. É útil cando hai que retirar repetidamente o elemento de maior (ou menor) prioridade, ou cando as insercións se intercalan con extraccións da raíz.
Unha implementación común é o montículo binario, no que a árbore é unha árbore binaria completa (véxase a figura). Foi introducido por J. W. J. Williams en 1964 para o algoritmo de ordenación heapsort. Os montículos úsanse en algoritmos de grafos como o algoritmo de Dijkstra. Un montículo binario non baleiro con nós ten altura , contada en arestas. Esta cota débese á súa forma completa, non só á propiedade de orde do montículo.
Como mostra a imaxe, non hai unha ordenación implícita entre irmáns nin curmáns, nin unha secuencia implícita para un percorrido en orde. A relación do montículo mencionada arriba só se aplica entre os nós e os seus pais e avós. O número máximo de fillos de cada nó depende do tipo de montículo.
Os montículos constrúense habitualmente no mesmo vector onde se almacenan os elementos, coa súa estrutura implícita no patrón de acceso das operacións. Nisto diferéncianse doutras estruturas con cotas teóricas similares ou mesmo mellores, como as árbores radix, en que non requiren memoria adicional alén da usada para gardar as chaves.
Operacións As operacións habituais son: Básicas find-max (ou find-min): atopar o elemento máximo dun montículo máximo, ou o mínimo dun mínimo (tamén chamado peek). insert: engadir unha nova chave ao montículo (tamén pushThe Python Standard Library, 8.4. heapq — Heap queue algorithm, heapq.heappush). extract-max (ou extract-min): devolver o nó de valor máximo (ou mínimo) tras retiralo do montículo (tamén popThe Python Standard Library, 8.4. heapq — Heap queue algorithm, heapq.heappop). delete-max (ou delete-min): retirar o nó raíz dun montículo máximo (ou mínimo). replace: extraer a raíz e inserir unha nova chave. É máis eficiente ca un pop seguido dun push, porque só hai que equilibrar unha vez, e é axeitado para montículos de tamaño fixo.The Python Standard Library, 8.4. heapq — Heap queue algorithm, heapq.heapreplace
Creación create-heap: crear un montículo baleiro. heapify: crear un montículo a partir dun vector de elementos. merge (union): unir dous montículos nun novo montículo válido con todos os seus elementos, conservando os orixinais. meld: unir dous montículos nun novo montículo válido con todos os seus elementos, destruíndo os orixinais.
Inspección size: devolver o número de elementos do montículo. is-empty: devolver verdadeiro se o montículo está baleiro.
Internas increase-key ou decrease-key: actualizar unha chave nun montículo máximo ou mínimo. delete: borrar un nó arbitrario (movendo despois o último nó e cribando para manter a propiedade). sift-up: mover un nó cara arriba na árbore, o necesario; úsase para restaurar a propiedade tras unha inserción. sift-down: mover un nó cara abaixo, similar ao sift-up; úsase para restaurar a propiedade tras un borrado ou unha substitución.
Implementación con vectores Os montículos adoitan implementarse cun vector: cada elemento do vector representa un nó do montículo, e a relación pai/fillo defínese implicitamente polos índices dos elementos no vector.
miniatura|upright=1.5|alt=Exemplo dun montículo máximo binario completo e como se almacenaría nun vector.|Exemplo dun montículo máximo binario completo con chaves enteiras de 1 a 100 e como se almacenaría nun vector. Para un montículo binario, o primeiro índice contén a raíz. Os dous índices seguintes conteñen os fillos da raíz; os catro seguintes, os fillos deses dous nós, e así sucesivamente. Por tanto, dado un nó no índice , os seus fillos están nos índices e , e o seu pai no índice nun vector que comeza en 0; ou ben , e nun que comeza en 1. Este simple esquema de indexación fai eficiente percorrer a árbore cara arriba ou cara abaixo.
O equilibrio do montículo faise con operacións de sift-up ou sift-down (intercambiando elementos fóra de orde). Como se pode construír un montículo a partir dun vector sen memoria adicional, o heapsort pode ordenar un vector in situ.
Despois de inserir ou borrar un elemento, a propiedade do montículo pode violarse e hai que restablecela intercambiando elementos dentro do vector. A forma máis común é: Inserción engadir o novo elemento ao final do montículo, no primeiro oco libre. Se iso viola a propiedade, cribar o novo elemento cara arriba ata restablecela. Extracción retirar a raíz e poñer nela o último elemento do montículo. Se iso viola a propiedade, cribar a nova raíz cara abaixo ata restablecela. Substitución retirar a raíz, poñer nela o novo elemento e cribar cara abaixo. Fronte á extracción seguida dunha inserción, isto evita un paso de criba cara arriba.
A construción dun montículo binario (ou -ario) a partir dun vector pode facerse en tempo linear co clásico algoritmo de Floyd, cun número de comparacións no peor caso igual a (para un montículo binario), onde é a suma dos díxitos da representación binaria de e é o expoñente de 2 na factorización de .. Isto mellora a cota no peor caso dunha secuencia de insercións consecutivas nun montículo baleiro, que é .A inserción número ten custo no peor caso . A suma das alturas máximas é ; hai secuencias que obrigan a realizar un número proporcional de ascensos. Isto non significa que toda secuencia de insercións leve tempo log-linear: algunhas poden ser lineares.
Variantes Montículo 2-3 B-heap Beap Montículo binario Montículo binomial Cola de Brodal Montículo d-ario Montículo de Fibonacci Montículo K-D Montículo de folla Montículo leftista Montículo binomial sesgado Montículo de Fibonacci estrito Montículo mínimo-máximo Montículo de emparellamento Montículo radix Montículo meldable aleatorizado Montículo sesgado Montículo suave Montículo ternario Treap Montículo débil
Comparación de cotas teóricas das variantes As distintas variantes difiren nas cotas asintóticas das súas operacións. Para fixo, os montículos binarios e -arios ofrecen inserción e extracción en e construción en . Os montículos binomiais, de Fibonacci e de emparellamento permiten fusións eficientes. O de Fibonacci acada custos amortizados para inserción, consulta do mínimo, fusión e diminución de chave dun nó localizado, e para a extracción do mínimo e o borrado dun nó localizado.
Aplicacións A estrutura de montículo ten moitas aplicacións: Heapsort: un dos mellores métodos de ordenación, in situ e sen casos cuadráticos no peor caso. Algoritmos de selección: un montículo permite consultar o extremo en tempo constante. Nun montículo mínimo binario, o algoritmo especializado de Frederickson selecciona o -ésimo menor elemento en . Non consiste en realizar simplemente extraccións. Aplicado á mediana, con , dá tempo . Algoritmos de grafos: os montículos poden mellorar as operacións da cola de prioridade en algoritmos como o algoritmo de Prim e o algoritmo de Dijkstra. A mellora depende da estrutura escollida e da densidade do grafo; non hai unha redución polinómica universal. Por exemplo, con montículos de Fibonacci estes algoritmos acadan a cota . Cola de prioridade: unha cola de prioridade é un concepto abstracto, como «unha lista» ou «un mapa»; así como unha lista se pode implementar cunha lista ligada ou un vector, unha cola de prioridade pódese implementar cun montículo ou outros métodos. Fusión k-aria: un montículo é útil para fusionar moitas secuencias xa ordenadas nunha soa. Exemplos son a ordenación externa e os resultados en fluxo de datos distribuídos. O bucle interno consiste en obter o mínimo, substituílo polo seguinte elemento da secuencia correspondente e facer unha operación de criba cara abaixo.
Implementacións nas linguaxes de programación A biblioteca estándar de C++ ofrece os algoritmos make_heap, push_heap e pop_heap para montículos (habitualmente binarios), que operan sobre iteradores de acceso aleatorio. Tamén ofrece a clase std::priority_queue. Non hai soporte estándar para as operacións de substitución, criba cara arriba/abaixo nin de diminución/aumento de chave. As bibliotecas Boost inclúen unha biblioteca de montículos. A diferenza da STL, admite diminución e aumento de chave, e tipos adicionais de montículo: -ario, binomial, de Fibonacci, de emparellamento e sesgado. A biblioteca estándar da linguaxe D inclúe std.container.BinaryHeap. Para Haskell existe o módulo Data.Heap. A plataforma Java (desde a versión 1.5) ofrece unha implementación de montículo binario coa clase PriorityQueue no Java Collections Framework. Por defecto implementa un montículo mínimo. Python ten un módulo heapq que implementa unha cola de prioridade cun montículo binario, con funcións para a fusión k-aria. PHP ten montículos máximo (SplMaxHeap) e mínimo (SplMinHeap) desde a versión 5.3. Perl ten implementacións de montículos binarios, binomial e de Fibonacci na distribución Heap de CPAN. A linguaxe Go contén un paquete heap con algoritmos que operan sobre un tipo que satisfai unha interface dada. A biblioteca Core Foundation de Apple contén a estrutura CFBinaryHeap. Pharo ten unha implementación dun montículo no paquete Collections-Sequenceable. A linguaxe Rust ten BinaryHeap, un montículo máximo binario, no módulo collections da súa biblioteca estándar. .NET ten a clase PriorityQueue, que usa unha implementación de montículo mínimo cuaternario (-ario), dispoñible desde .NET 6.
Notas
Véxase tamén Bibliografía Jon Louis Bentley. Programming Pearls, segunda edición, Addison Wesley, 2000, páxinas 147–162. ISBN 0201657880.
Outros artigos Algoritmo de ordenación Cola de prioridade Montículo binario Treap
Ligazóns externas Montículos en Wikimedia Commons Heap en Wolfram MathWorld Explicación de como funcionan os algoritmos básicos de montículo
Categoría:Algoritmos Categoría:Programación