- Сортирующее дерево
-
Сортирующее дерево
- Это статья о структуре данных. Статья об области нераспределённой памяти при динамическом распределении памяти называется Куча (нераспределённая память).
Сортирующее дерево (куча, пирамида) — такое двоичное дерево, для которого выполнены два условия:
- Каждый лист имеет глубину либо 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
См. также
Ссылки
- Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. Глава 6. Пирамидальная сортировка // Алгоритмы: построение и анализ = Introduction to Algorithms / Под ред. И. В. Красикова. — 2-е изд. — М.: Вильямс, 2005. — С. 178 - 193. — ISBN 5-8459-0857-4
Wikimedia Foundation. 2010.
Пирамидальная сортировка — Анимированная схема алгоритма Пирамидальная сортировка (англ. Heapsort, «Сортировка кучей»[1]) … Википедия
Куча (программирование) — Это статья о структуре данных. Статья об области нераспределённой памяти при динамическом распределении памяти называется Куча (нераспределённая память). пример сортирующего дерева Сортирующее дерево (куча, пирамида) такое двоичное дерево, для… … Википедия
Куча (значения) — В Викисловаре есть статья «куча» Куча нагромождение большого количества объектов, по форме обычно похожее на конус. В переносном смысле большое количество чего либо. См. парадокс кучи. Содержание … Википедия