Определение кучи

Итак, во всех простых решениях по крайней мере одна из операций выполняется за время O(n) — это намного больше времени О(log n), на которое мы надеялись. На помощь приходит куча — структура данных, в нашем контексте сочетающая преимущества сортированного массива и списка.
На концептуальном уровне куча может рассматриваться как сбалансированное бинарное дерево (слева на рис. 2.3). У дерева имеется корень, а каждый узел может иметь до двух дочерних узлов: левый и правый. Говорят, что ключи такого бинарного дерева следуют в порядке кучи, если ключ каждого элемента по крайней мере не меньше ключа элемента его родительского узла в дереве. Другими словами,

Порядок кучи: для каждого элемента v в узле i элемент w родителя i удовлетворяет условию key(w) < key(v).

На рис. 2.3 числа в узлах определяют ключи соответствующих элементов.

Рис. 2.3. Куча в виде бинарного дерева (слева) и в виде массива (справа). Стрелками обозначены дочерние узлы трех верхних узлов дерева


Прежде чем обсуждать работу с кучей, следует определиться со структурой данных, которая будет использоваться для ее представления. Можно использовать указатели: каждый узел содержит элемент, его ключ и три указателя (два дочерних узла и родительский узел). Однако если заранее известна граница N общего коли- чества элементов, находящихся в куче в любой момент времени, можно обойтись и без указателей. Такие кучи могут храниться в массиве H с индексами i = 1, ..., N. Узлы кучи соответствуют позициям в массиве. H[1] представляет собой корневой узел, а для любого узла в позиции i его дочерние узлы находятся в позициях leftChild(i) = 2i и rightChild(i) = 2i + 1. Таким образом, два дочерних узла корня находятся в позициях 2 и 3, а родитель узла в позиции i находится в позиции parent(i) = iП\. Если куча в какой-то момент содержит n < N элементов, то первые n позиций массива используются для хранения n элементов кучи, а количество элементов в H обозначается length(H). С таким представлением куча в любой мо- мент времени является сбалансированной. В правой части рис. 2.3 показано пред- ставление в виде массива для кучи, изображенной в левой части.

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

Еще по теме Определение кучи:

  1. Статья 55. Лишение права занимать определенные должности или заниматься определенной деятельностью
  2. 2. Лишение права занимать определенные должности или заниматься определенной деятельностью
  3. 2. Вещи, определенные родовыми признаками, и индивидуально-определенные вещи
  4. § 33 Общее правило о переходе наследства к детям. – Отличие отделенных от неотделенных. – Право представления. – Право родительское. – Право боковых родственников. – Римская система определения прав по классам и степеням. – Германская система определения прав по линиям и коленам.
  5. 1. Определение
  6. § 4. Определения арбитражного суда
  7. Варианты определений
  8. 1. Определение сделки
  9. Определение команды.
  10. Определение объема выборки.
  11. Определение организации.
  12. Определение социальной группы.
  13. ОПРЕДЕЛЕНИЕ ПОНЯТИЯ
  14. Определение ситуации