Стак срещу купчина
Стека е подреден списък, в който вмъкването и изтриването на елементи от списъка може да се извършва само в единия край, наречен горен. Поради тази причина стекът се счита за структура от данни „Последен влязъл, първи излязъл“(LIFO). Heap е специална структура от данни, която се основава на дървета и отговаря на специално свойство, наречено свойство heap. Освен това купчината е пълно дърво, което означава, че няма празнини между листата на дървото, т.е. в пълно дърво всяко ниво се попълва преди добавяне на ново ниво към дървото и възлите в дадено ниво се запълват от отляво надясно.
Какво е Stack?
Както споменахме по-рано, стекът е структура от данни, в която елементите се добавят и премахват само от единия край, наречен отгоре. Стековете позволяват само две основни операции, наречени push и pop. Операцията push добавя нов елемент в горната част на стека. Операцията pop премахва елемент от върха на стека. Ако стекът вече е пълен, когато се извърши операция за изтласкване, това се счита за препълване на стека. Ако изскачаща операция се извърши върху вече празен стек, това се счита за препълване на стека. Поради малкия брой операции, които могат да бъдат извършени върху стека, той се счита за структура с ограничени данни. Освен това, според начина, по който са дефинирани операциите push и pop, е ясно, че елементите, които са добавени последни в стека, излизат от стека първи. Следователно стекът се счита за структура от данни LIFO.
Какво е Heap?
Както споменахме по-рано, heap е цялостно дърво, което удовлетворява свойството heap. Свойството Heap гласи, че ако y е дъщерен възел на x, тогава стойността, съхранена във възел x, трябва да бъде по-голяма или равна на стойността, съхранена във възел y (т.е. стойност(x) ≥ стойност(y)). Това свойство предполага, че възелът с най-голяма стойност винаги ще бъде поставен в основата. Купчина, конструирана с помощта на това свойство, се нарича max-heap. Има друга разновидност на свойството heap, която заявява обратното на това. (т.е. стойност(x) ≤ стойност(y)). Това означава, че възелът с най-малка стойност винаги ще бъде поставен в основата, което се нарича min-heap. Има широк спектър от операции, извършвани върху купчини, като намиране на минимум (в мин. купчини) или максимум (в макс. купчини), изтриване на минимум (в мин. купчини) или максимум (в макс. купчини), увеличаване (в макс. -heaps) или намаляващ (в min-heaps) ключ и т.н.
Каква е разликата между Stack и Heap?
Основната разлика между стекове и купчини е, че докато стекът е линейна структура от данни, купчината е нелинейна структура от данни. Стекът е подреден списък, който следва свойството LIFO, докато купчината е пълно дърво, което следва свойството на купчината. Освен това стекът е ограничена структура от данни, която поддържа само ограничен брой операции като push и pop, докато heap поддържа широк набор от операции като намиране и изтриване на минимум или максимум, увеличаване или намаляване на ключа и сливане.йени
