Stack vs Heap
Stack yog ib daim ntawv xaj uas tso thiab tshem tawm cov npe khoom tuaj yeem ua tiav hauv ib kawg hu ua saum. Vim li no, pawg yog suav tias yog Qhov Kawg Hauv Thawj Tawm (LIFO) cov ntaub ntawv qauv. Heap yog cov ntaub ntawv tshwj xeeb uas tsim los ntawm cov ntoo thiab nws txaus siab rau cov cuab yeej tshwj xeeb hu ua heap cuab yeej. Tsis tas li ntawd, ib lub heap yog ib tsob ntoo tiav, uas txhais tau hais tias tsis muaj qhov khoob ntawm nplooj ntawm tsob ntoo, piv txwv li hauv tsob ntoo tiav txhua qib tau sau ua ntej ntxiv qib tshiab rau tsob ntoo thiab cov nodes hauv ib qib tau sau los ntawm sab laug mus rau sab xis.
Stack yog dab tsi?
Raws li tau hais ua ntej lawm, pawg yog cov ntaub ntawv cov qauv hauv cov ntsiab lus ntxiv thiab tshem tawm tsuas yog ib qho kawg hu ua sab saum toj. Stacks cia tsuas yog ob qho haujlwm tseem ceeb hu ua thawb thiab pop. Kev ua haujlwm thawb ntxiv ib qho tshiab rau saum pawg. Kev ua haujlwm pop tshem tawm cov khoom los ntawm sab saum toj ntawm pawg. Yog tias pawg twb tau puv lawm, thaum lub tshuab thawb ua haujlwm, nws raug suav hais tias yog pawg dhau. Yog tias lub lag luam pop tau ua tiav ntawm ib pawg uas twb muaj lawm, nws raug suav hais tias yog pawg hauv qab. Vim muaj cov haujlwm me me uas tuaj yeem ua rau ntawm pawg, nws raug suav tias yog cov ntaub ntawv txwv. Tsis tas li ntawd, raws li txoj kev uas lub laub thiab pop ua haujlwm tau txhais, nws yog qhov tseeb tias cov ntsiab lus uas tau ntxiv rau hauv cov pawg mus tawm ntawm pawg thawj zaug. Yog li pawg yog suav tias yog LIFO cov ntaub ntawv qauv.
Hnub yog dab tsi?
Raws li tau hais ua ntej, heap yog tsob ntoo tiav uas txaus siab rau cov khoom heap. Heap cov cuab yeej hais tias, yog tias y yog tus menyuam ntawm x ces tus nqi khaws cia hauv qhov x yuav tsum ntau dua lossis sib npaug rau tus nqi khaws cia hauv qhov y (piv txwv li tus nqi (x) ≥ tus nqi (y)). Cov cuab yeej no txhais tau hais tias cov node nrog tus nqi loj tshaj plaws yuav tsum tau muab tso rau ntawm lub hauv paus. Ib heap tsim siv cov cuab yeej no hu ua max-heap. Muaj lwm qhov kev hloov pauv ntawm cov cuab yeej heap uas hais txog qhov rov qab ntawm qhov no. (i.e. tus nqi(x) ≤ tus nqi(y)). Qhov no txhais tau hais tias cov node nrog tus nqi tsawg tshaj plaws yuav tsum tau muab tso rau ntawm lub hauv paus, yog li hu ua min-heap. Muaj ntau yam kev ua haujlwm ua haujlwm ntawm heaps xws li nrhiav qhov tsawg kawg nkaus (hauv min-heaps) lossis siab tshaj (hauv max-heaps), tshem tawm yam tsawg kawg nkaus (hauv min-heaps) lossis siab tshaj (hauv max-heaps), nce (hauv max. -heaps) lossis txo qis (hauv min-heaps), thiab lwm yam.
Dab tsi yog qhov txawv ntawm Pawg thiab Heap?
Qhov sib txawv tseem ceeb ntawm pawg thiab heaps yog tias thaum pawg yog cov qauv ntaub ntawv, heap yog cov ntaub ntawv tsis muaj kab. Stack yog ib daim ntawv teev npe uas ua raws li LIFO cov cuab yeej, thaum lub heap yog ib tsob ntoo tiav uas ua raws cov cuab yeej heap. Tsis tas li ntawd, pawg yog cov ntaub ntawv txwv cov qauv uas txhawb nqa tsuas yog qee qhov kev ua haujlwm xws li thawb thiab pop, thaum heap txhawb nqa ntau yam haujlwm xws li nrhiav thiab tshem tawm qhov tsawg kawg nkaus lossis siab tshaj, nce lossis txo tus yuam sij thiab sib koom ua ke.
