IPB

Здравейте ( Вход | Регистрация )

 
Reply to this topicStart new topic
> Heap data structure, или така наречената на български пирамида
secretk
коментар Sep 18 2009, 08:50
Коментар #1


Редовен Потребител

Група: Потребител +
Коментари: 558
Регнат: 20-March 08
От: София
Пол: Жена



Може въпроса ми да ви се стори тъп и се извинявам за това, но имам следния проблем.
Имам дипломна защита в скоро време, темата и беше структурата от данни heap и нейната имплементация.
Като трябваше да се направи една програма за визуализация на heap на java.
Heap-ът не е сложна структура и има две важни операции за имплементация - добавяне на нов елемент и изтриване на корена на дървото.
Навсякъде, където намерих информация по книги, лекции и в мрежата, алгоритъма за премахване на корен от heap е следния:
1. Корена се разменя с последния елемент в heap-а
2. Премахва се последния елемент от heap-а
3. Прави се функци percolateDown, чиято цел е да превърне дървото отново в heap.

Това е идеята и е с цел цената на премахването да е О(log n). Преподавателят обаче не иска да се съгласи, че това е така. Неговата идея е, че не трябва да се разместват корена и последния елемент, а просто да се премахне първия елемент и на негово да място да се слага един елемент от по-долното ниво(максималния или минималния в зависимост от вида на heap-a).
Потърсих доста в мрежата, но никъде няма такава идея за имплементация, но никъде не намерих и обяснение защо се прави тази размяна.
Тъй като вероятността да ми зададе този въпрос на защитата е доста голям, ви моля да ми дадете някакви идеи как да се аргументирам.
Да поясня, че за имплементацията на хеап ползвам Vector, а не array, който е доста подходящ за пълно двоично дърво, каквото е heap-а, поради факта, че ползвам нишки и ми трябва синхронизация.
Благодаря предварително за помощта!
Go to the top of the page
 
+Quote Post

Reply to this topicStart new topic
1 потребител(и) четат тази тема (1 гости и 0 скрити)
0 Потребител(и):

 



- Елате в .: BGtop.net :. Топ класацията на българските сайтове и гласувайте за този сайт!!! Олекотена версия

Сега е: 16th September 2019 - 05:05