Heap

Heap [Havaĵo] (datumstrukturo)

El Vikipedio, la libera enciklopedio

fonto: http://en.wikipedia.org/wiki/Heap_%28data_structure%29

Ĉi tiu artikolo estas pri la programada datumstrukturo. Por la dinamika memora areo, vidu atribuo de Dinamika memoro.

Ekzemplo de kompletaj duumaj max-amaso

 

En komputika scienco, heap estas specialigita arbo bazita datumstrukturo kiu kontentigas la havaĵan propraĵon: Se A estas nodo-patro de B tiam ŝlosilo (A) estas ordigita kun respekto al klavo (B) kun la sama ordigo apliki tra la amaso . Ĉu la klavoj de patraj nodoj estas ĉiam pli granda ol aŭ egala al tiuj de la infanoj kaj la plej alta klavo estas en la radika vertico (ĉi tiu speco de havaĵo estas nomata max amaso) aŭ la ŝlosilojn de patraj nodoj estas malpli ol aŭ egala al tiuj de la infanoj (heap-min).
Notu ke, kiel montrita en la grafika, ne estas implicita ordo inter gefratoj aŭ gekuzoj kaj neniu implicita sinsekvas por en-orda traversal (kiel estus en, ekzemple, la duuma serĉarbo ). La amasa rilato menciita supre validas nur inter nodoj kaj ilia tuja gepatroj.
La maksimuma nombro de infanoj ĉiu nodo povas havi dependas de la tipo de amaso, sed en multaj tipoj estas maksimume du. La heap estas unu maksimume efika efektivigo de abstrakta datumtipo nomata prioritata vosto. Amasoj estas krita en pluraj efikaj grafeaj algoritmoj tiaj kiel Dijkstra algoritmo, kaj en la ordiga algoritmo heapsort.
Heap-datumstrukturo devus ne esti konfuzita kun la heap, kiu estas komuna nomo por dinamikaj asignitaj memoroj. La termino estis origine uzita nur por la datumstrukturo.

Enhavo 1 Apliko kaj operacioj 2 Variantoj 3 Komparo de teoriaj baroj por variantoj 4 Aplikoj 5 Kiel skribi 6 Vidu ankaŭ 7 Referencoj 8 Eksteraj ligiloj

Apliko kaj operacioj

Amasoj estas kutime realigita en tabelo, kaj ne postulas punteros inter elementoj.
La operacioj komune agis kun amaso estas:

• krei-heap: krei malplenajn heap
• (Varianto) krei-heap: krei amason el donita tabelo de elementoj
• trovi-max aŭ trovi-min: trovi la maksimuman eron de heap-max aü minimuman eron de heap-min, respektive
• delete-max aŭ delete-min: forigante la radika nodo de heap-max aŭ heap-min, respektive
• kreski-klavo aŭ malkreki-ŝlosilo: ĝisdatigo kerna ene de heap-max aŭ heap-min, respektive
• enŝovi: aldoni novan ŝlosilon al la havaĵo
• kunfandi: kunigi du amasojn formante validan novan amason enhavas ĉiujn elementojn de ambaŭ.

Malsamaj tipoj de amasoj apliki la operaciojn en malsamaj manieroj, sed rimarkinde, adicii estas ofte farita per aldono de la nova elemento en la fino de la amaso en la unua disponebla libera spaco. Ĉi emos seksperforti la heap-proprieton, kaj do la elementoj estas do reordigita ĝis la mura proprieto estis restarigita. Konstruu binara (aŭ d-_ara_) heap donante tabelo de elementoj povas esti formita rapide ol vico de sinsekvaj adicioj en origine malplenan amason uzante la klasika Floyd-ejon algoritmo, kun la plej malbona-kaza nombro de komparoj egala al 2N-2s ₂ (N) - e ₂ (N) (por duargumenta amaso), kie s ₂ (N) estas la sumo de ĉiuj ciferoj de la duuma prezento de n kaj e ₂ (N) estas la eksponento de 2 en la prima faktorigo de N. ^[1]

Variantoj

• heap-2-3
• Beap
• heap-Duuma
• heap-Binoma 
• Brodal vosto
• D-_ary_ amaso
• Fibonaĉi amaso
• Maldekstrismaj amaso
• Emparejamiento amaso
• Dekliva muro
• Mola amaso
• Malforta amaso
• Folio amaso
• Radix amaso
• Hazardigita meldable amaso

Komparu de teoriaj baroj por variantoj

La jenaj tempo complejidades ^[2] estas amortizita (plej malbona-tempo) tempa komplekseco por enskriboj markita de asterisko, kaj regula plej malbona kazo tempo complejidades por ĉiuj aliaj elementoj. O (f) donas asimptota supera baro kaj Θ (f) estas asimptote strikta baro (vidu Granda a skribmaniero ). Funkcio nomoj alpreni min-amaso.

Operacio	Duuma [2]	Binoma [2]	Fibonacci [2]	Emparejamiento [3]	Brodal *** [4]	RP [5]
trovi-min	Θ (1)	Θ (1)	Θ (1)	Θ (1)	Θ (1)	Θ (1)
delete-min	Θ (log n)	Θ (log n)	O (log n) *	O (log n) *	O (log n)	O (log n) *
enigi	Θ (log n)	O (log n)	Θ (1)	Θ (1) *	Θ (1)	Θ (1)
malpliigo-klavo	Θ (log n)	Θ (log n)	Θ (1) *	O (log n) *	Θ (1)	Θ (1) *
kunfandi	Θ (n)	O (log n) **	Θ (1)	Θ (1) *	Θ (1)	Θ (1)

(*) Amortizita tempo
(**) Kie n estas la grandeco de la pli granda amaso
(***) Brodal kaj Okasaki poste priskribi konstanta varianto kun la sama baroj krom malkresko-ŝlosilo, kiu ne estas subtenata. Amasoj kun n elementoj povas esti konstruita fundo-supren en O (n). ^[6]

Aplikoj

La heap-datumstrukturo havas multajn aplikojn.

• Heapsort : Unu el la plej bonaj metodoj ordigi esti en-loko kaj sen kvadrata plej malbonaj kazaj scenejoj.
• Selekti algoritmojn: Trovanta la min, max, tiel la min, kaj max, mezo, aŭ eĉ la k-a plej granda ero povas esti farita en lineara tempo (ofte konstantan tempo) uzante amasoj. ^[7]
• Grafikaĵaj algoritmoj : Uzante amasoj kiel interna traversalaj datumstrukturoj, tempo de ekzekuto estos reduktitaj de polinoma ordo. Ekzemploj de tiaj problemoj estas Prim minimuma generanta arba algoritmo kaj Dijkstra la plej mallonga voja problemo .

Plena kaj preskaŭ plena duumaj amasoj povas esti prezentita en tre spaco-efika maniero uzante tabelo nur. La unua (aŭ lasta) elemento enhavos la radikon. La sekvaj du elementoj de la tabelo enhavas liaj filoj. La sekvantaj kvar enhavas la kvar infanoj de la du infanaj verticoj, ktp. Tial la nodaj filoj en la pozicio n estus en pozicioj 2n kaj 2n+1 en unu bazita tabelo, aŭ 2n+1 kaj 2n+2 en nulo-bazita tabelo. Tio ebligas movi supren aŭ malsupren de la arbo farante simplaj indeksaj kalkuladoj. Balanci heap estas farita per interŝanĝi elementojn, kiuj estas el ordo. Kiel ni povas konstrui unu tabelo sen postuli superfluan memoron (por la nodoj, ekzemple), heapsort povas esti uzata por ordigi tabelon.

Kiel skribi

• La C++ Standard Ŝablona Biblioteko provizas la make_heap, push_heap kaj pop_heap algoritmoj por heap (kutime implementado kiel duumaj amasoj), kiu operacias sur ajna hazarda aliro Iteriloj . Ĝi traktas la Iterilojn kiel referenco al tabelo, kaj uzas la tabelo-al-heap konvertiĝo. Uja adaptilo priority_queue ankaŭ ekzistas. Tamen, ne estas norma subteno por la malkresko/kresko-ŝlosila operacio. Vidu ankaŭ gheap - STL-kiel ĝeneraligita amaso efektivigo en C++ kun D-amaso kaj B-amaso subteno.
• La Java2a platformo (ekde versio 1.5) provizas la duuman efektivigo de Heap kun klaso java.util.PriorityQueue <E> en Java Kolektoj Framework.
• Python havas heapq modulo kiu implementa prioritato queue uzanta duuma amaso.
• PHP havas ambaŭ maxheap (SplMaxHeap) kaj minheap (SplMinHeap) ekde versio 5.3 en la Standardo PHPa Biblioteko.
• Perl havas heap de skribita duuma, duterma, kaj Fibonaccia en la heap-dissendo disponebla en CPAN.
• La Go biblioteko enhavas pako de Heap kun amasaj algoritmoj kiuj operacias sur ajna tipo kiu kontentigis donitan interfacon.
• Apple Core Fondaĵa biblioteko enhavas CFBinaryHeap-strukturon.