Структура данных кучи - PullRequest
Новая
       3

Структура данных кучи

4 голосов
/ 22 марта 2010

Попытка придумать нижнюю границу для положения, скажем, n-го по величине ключа в max-heap. Предполагая, что куча выложена в массиве. Думаю, верхняя граница min (2 ^ n-2, размер массива -1), но всегда ли она ограничена нижней границей 0?

1 Ответ

0 голосов
/ 22 марта 2010

Первоначальное исследование проблемы показывает следующее соотношение между n и нижней и верхней границами (при условии, что в куче 14 элементов) 

n   lb  up
1   1   1
2   2   3
3   2   7
4   2   14
9   3   14
10  4   14
12  5   14
13  6   14
14  8   14

Чтобы определить число элементов, которые могут быть больше, чемэлемент в определенном месте массива кучи, рассчитать размер поддерева, укорененного в этом месте.Эти два числа затем связываются по формуле 

# of elements possible larger  = total number of elements - size of subtree - 1

РЕДАКТИРОВАТЬ: Обратите внимание, что расчет выполняется в обратном направлении.Учитывая позицию в массиве / куче, можно определить, в какой позиции будет значение, если куча была отсортирована.Учитывая узел, куча может быть разделена на три раздела:

  1. Элементы, которые гарантированно будут больше, чем текущий элемент (родитель, родительский родитель, ...)
  2. Элементы, которые гарантированно будут меньше текущего элемента (поддерево укоренено в текущем элементе)
  3. Остальные элементы, которые могут быть больше или меньше текущего элемента.

Если мы рассмотрим пример кучи с 14 элементами и хотим определить диапазон возможных значений в 6-м местоположении, группы будут следующими:

  • Группа 1 содержит два элемента (3, 1)
  • Группа 2 содержит два элемента (12, 13)
  • Группа 3 содержит остальные девять элементов (исключая текущее значение) (2, 4, 5, 7, 8, 9, 10, 11, 14)

Следовательно, нижняя граница равна 3 (количество элементов в первой группе + 1), а верхняя граница равна 11 (количество элементов в первой группе + количество элементов в третьей группе + 1).

...