Реализация модуля Heapq - PullRequest
Новая
       42

Реализация модуля Heapq

0 голосов
/ 29 ноября 2018

Я читал исходный код модуля heapq, потому что я рассмотрел вопрос на CodeReview и не могу что-то понять.

В статье в Википедии о куче говорится:

sift-up: перемещать узел вверх по дереву столько, сколько нужно;используется для восстановления состояния кучи после вставки.Вызывается "просеять", потому что узел перемещается вверх по дереву, пока не достигнет правильного уровня, как в сите.

sift-down: переместить узел вниз по дереву, аналогично sift-up;используется для восстановления состояния кучи после удаления или замены.

Но код heappush ( исходный код ): 

def heappush(heap, item):
    """Push item onto heap, maintaining the heap invariant."""
    heap.append(item)
    _siftdown(heap, 0, len(heap)-1)

Если я прочиталВикипедия справа, при вставке элемента, который я ожидал увидеть siftup, а не siftdown.

Аналогично для heappop ( источник здесь ): 

def heappop(heap):
    """Pop the smallest item off the heap, maintaining the heap invariant."""
    lastelt = heap.pop()    # raises appropriate IndexError if heap is empty
    if heap:
        returnitem = heap[0]
        heap[0] = lastelt
        _siftup(heap, 0)
        return returnitem
return lastelt

Из статьи в Википедии я ожидал вызова siftdown, но получил siftup.

Это ошибка в Википедии или в модуле heapq?Или мое понимание неверно?

1 Ответ

0 голосов
/ 30 ноября 2018

Как отмечено в комментариях, это проблема номенклатуры.Наиболее распространенная терминология называет корень «вершиной» дерева, а узлы на других уровнях находятся «ниже» корня.Мы рисуем дерево в этой ориентации.То есть: 

        1
    2       3
  4   5   6   7

В таком случае имеет смысл сказать, что переместить элемент из корня на более низкий уровень - это "просеивание вниз".

Вы можете сделать аргумент,как кто-то делал в комментариях, что перемещение чего-либо на более низкий уровень увеличивает его индекс в массиве поддержки, поэтому имеет смысл говорить об этом как о «просеивании».Но люди визуализируют модель дерева, а не реализацию массива.Говоря о модели, ваша терминология должна соответствовать модели.

Меня всегда немного раздражало, что автор heapq решил использовать нестандартную терминологию.Можно утверждать, что он говорит о реализации, но я оспариваю это.Комментарий гласит: «Поднять вверх: переместить узел вверх в дереве ...» Очевидно, он имеет в виду дерево модель .

Википедия, https://en.wikipedia.org/wiki/Tree_structure, говорит:

Древовидная структура или древовидная диаграмма - это способ представления иерархической природы структуры в графической форме.Она называется «древовидная структура», потому что классическое представление напоминает дерево, хотя диаграмма, как правило, перевернута вверх по сравнению с фактическим деревом, с «корнем» вверху и «листьями» внизу.

Эта тема обсуждалась до смерти в первые дни, возможно, наиболее известный Дональд Кнут в Искусство компьютерного программирования .См https://www.quora.com/Why-are-trees-in-computer-science-generally-drawn-upside-down-from-how-trees-are-in-real-life.

...