- Куча (программирование)
-
- Это статья о структуре данных. Статья об области нераспределённой памяти при динамическом распределении памяти называется Куча (нераспределённая память).
Сортирующее дерево (куча, пирамида) — такое двоичное дерево, для которого выполнены два условия:
- Каждый лист имеет глубину либо d либо d-1
- Значение в любой вершине больше (меньше), чем значения ее потомков.
Удобная структура данных для сортирующего дерева — такой массив Array, что Array[1] — элемент в корне, а потомки элемента Array[i] — Array[2i] и Array[2i+1].
Рассматривая кучу как дерево, определим 'высоту' ее узла как число ребер в самом длинном нисходящем простом пути от этого узла к какому-то из листьев дерева. Высота кучи есть высота ее корневого узла. Высота кучи равна .
Содержание
Базовые процедуры
В этом разделе представлены основные базовые процедуры для работы с кучей.
Heapify
Процедура Heapify служит для поддержки свойства кучи и выполняется за время .
Heapify(A, i) l <- i * 2 r <- i * 2 + 1 if l <= heap_size[A] и A[l] > A[i] then largest <- l else largest <- i if r <= heap_size[A] и A[r] > A[largest] then largest <- r if largest ≠ i then Обменять A[i] <-> A[largest] Heapify(A, largest)
Build_Heap
Эта процедура предназначена для создания кучи из неупорядоченного массива входных данных. Время работы равно .
Build_Heap(A) heap_size[A] <- length[A] for i <- floor(length[A] / 2) downto 1 do Heapify(A, i)
Heapsort
Процедура Heapsort сортирует массив без привлечения дополнительной памяти за время .
Heapsort(A) Build_Heap(A) for i <- length[A] downto 2 do Обменять A[1] <-> A[i] heap_size[A] <- heap_size[A] - 1 Heapify(A, 1)
Heap_Change_Key
Выполняет изменение элемента в куче за время .
Heap_Change_Key(a, i, key) A[i] <- key Heapify(A, i) while i > 1 и A[floor[i / 2]] < A[i] do Обменять A[i] <-> A[floor[i / 2]] i <- floor[i / 2]
Heap_Insert
Выполняет вставку в кучу за время .
Heap_Insert(A, key) heap_size[A] <- heap_size[A] + 1 A[heap_size[A]] <- key Heap_Change_Key(A, heap_size[A], key)
Heap_Extract
Выполняет извлечение из кучи за время .
Heap_Extract(A) if heap_size[A] < 1 then error "Куча пуста" max <- A[1] A[1] <- A[heap_size[A]] heap_size[A] <- heap_size[A] - 1 Heapify(A, 1) return max
См. также
Ссылки
- wikiSpaces.com
- Кормен, Томас Х., Лейзерсон, Чарльз И., Ривест, Рональд Л., Штайн, Клифорд Глава 6. Пирамидальная сортировка // Алгоритмы: построение и анализ, 2-е издание = Introduction to Algorithms second edition. — М.: «Вильямс», 2005. — С. 178 - 193. — ISBN 5-8459-0857-4
Wikimedia Foundation. 2010.