могили

Е, да, още веднъж за изпитите, отново за изучаването и стигам до раздел, в който казаното от книгата ме изненадва и, като го прилагам, се потвърждавам. Теорията или това, което се съдържа в книгите, не е 100% надеждна, в случай на математически, физически теории, ... или изчисления, трябва да проверим какво ни казват книгите, защото можем да намерим погрешен отпечатък.

Актуализиране: ако искате да видите как да направите кода на могилата с Elixir, можете да видите този запис.

Като се има предвид, че това, което посочва книгата, е псевдокод, то е още по-лошо, тъй като който го пише, със сигурност ще го направи добре и не се съмнявам, че дори го е проверил, но разбира се, ние го откриваме не е конкретен език, това може да бъде тълкуване на изпълнение, за което е възможно да се загуби някаква същност по пътя или да се извърши печатна грешка.

Но до точката. Могили.

Тази структура от данни е предложена от Робърт У. Флойд (награда на Тюринг през 1978 г.) за решаване на проблема с подреждането на елементи в даден вектор, известната купчина (или подреждане по купчина).

По предмета Програмиране и усъвършенствани структури от данни (в бакалавърската степен по компютърно инженерство в UNED) се предлага в началото на предмета, като познаване на структурите от данни, могилата.

Могилата, макар и концептуално нарисувана под формата на дърво, е изпълнена върху вектор. Тъй като е балансиран и двоичен, възелът може да съдържа само две деца. Формулата за достъп до всяко дете, като се има предвид индексът на родителя (i), ще бъде:

Достъпът до родителя ще бъде направен с цяло число деление: i/2 .

Самата могила позволява:

  • Поръчайте елементи на вектор по лесен и оптимален начин, като можете да внедрите персонализиран сравнител.
  • Търси максимумите, минимумите или всеки друг фактор, който да се вземе предвид при избора на елементи за търсене.
  • В специфични за графиката проблеми като минималното покритие на Prim или най-краткия път на Dijkstra.

Внедряване на алгоритъма

Отне ми малко време да реша езика, на който да го реализирам, накрая избрах Ruby, тъй като кодът му е доста псевдо кодиран, но би бил също толкова добър и в Python. Кодът ще бъде:

След като целият код бъде видян, можем да направим тест като следния, в който ще вмъкнем някои случайни данни и ще получим резултата от тяхното съхранение под формата на купчина, а резултата в подреден вектор:

Резултатът е както следва:

ЗАБЕЛЕЖКА: Както можете да видите в изпълнението, този код е подготвен за вектори, които са изброили своите елементи въз основа на 1.N, и въпреки това всички езици (с изключение на Pascal, Modula - 2 и други подобни) номерират векторите от 0.N - 1, така че при всеки достъп до атрибута @vector броят трябваше да бъде намален с 1, за да премине от обозначението 1.N до 0.N - 1.

Заключения