Метод на купчина, проливане надолу

В момента правя max-heap. Когато използвам метода remove(), разбирам, че бих разменил с по-големите деца. Ами ако и двете деца имат еднакъв приоритет? например

Случай 1:

куп = [5,7,7,16,15]

ако премахна 5 и го заменя с 15, ще се проточа надолу вдясно (което е грешно), така че ще се процедя надолу в лявата страна.

но използвайки същата логика, ако имам

куп = [5,7,7,16,15,18]

и се процеждам надолу наляво, вече няма да е валидна купчина.

Какво мога да направя, за да се уверя, че имам валидна купчина?


heap max-heap
person Sugihara    schedule 24.05.2013    source източник
comment
Как е това max-heap? Ако 5 е горният елемент, това не е ли min-heap?   -  person Patashu    schedule 24.05.2013

Отговори (1)


arrow_upward
0
arrow_downward

Няма значение.

Процеждането надолу надясно в първия случай е добре:

[15, 7, 7, 16] -> [7, 7, 15, 16]

Процеждането надолу вляво в първия случай е добре:

[15, 7, 7, 16] -> [7, 15, 7, 16]

Процеждането надолу надясно във втория случай е добре:

[18, 7, 7, 16, 15] -> [7, 7, 18, 16, 15]

Процеждането наляво във втория случай е добре:

[18, 7, 7, 16, 15] -> [7, 18, 7, 16, 15] -> [7, 15, 7, 16, 18]

person Stefan Haustein    schedule 24.05.2013