Операции с двоичной кучей (обычно используемой реализацией) имеют следующую сложность:
Вставка элемента (Insert): O(log n). Новый элемент добавляется в конец, а затем выполняется операция "всплывания" (heapify up) для восстановления свойств кучи. В худшем случае всплывание происходит до корня, что логарифмично по высоте дерева.
Удаление минимального/максимального элемента (Extract-Min/Max): O(log n). Корневой элемент (минимальный/максимальный) удаляется, последний элемент помещается на его место, а затем выполняется операция "просеивания вниз" (heapify down) для восстановления свойств кучи. В худшем случае просеивание происходит до листа.
Просмотр минимального/максимального элемента (Peek/Top): O(1). Минимальный/максимальный элемент находится в корне кучи и доступен напрямую.
Построение кучи из массива (BuildHeap): O(n). Несмотря на то, что каждый вызов h
Операции с двоичной кучей (обычно используемой реализацией) имеют следующую сложность:
Вставка элемента (Insert): O(log n). Новый элемент добавляется в конец, а затем выполняется операция "всплывания" (heapify up) для восстановления свойств кучи. В худшем случае всплывание происходит до корня, что логарифмично по высоте дерева.
Удаление минимального/максимального элемента (Extract-Min/Max): O(log n). Корневой элемент (минимальный/максимальный) удаляется, последний элемент помещается на его место, а затем выполняется операция "просеивания вниз" (heapify down) для восстановления свойств кучи. В худшем случае просеивание происходит до листа.
Просмотр минимального/максимального элемента (Peek/Top): O(1). Минимальный/максимальный элемент находится в корне кучи и доступен напрямую.
Построение кучи из массива (BuildHeap): O(n). Несмотря на то, что каждый вызов h
Register or sign in to get access to full answers for all questions from the question bank.