Сортирующее дерево

Сортирующее дерево

Это статья о структуре данных. Статья об области нераспределённой памяти при динамическом распределении памяти называется Куча (нераспределённая память).

пример сортирующего дерева

Сортирующее дерево (куча, пирамида) — такое двоичное дерево, для которого выполнены два условия:

1. Каждый лист имеет глубину либо d либо d-1
2. Значение в любой вершине больше (меньше), чем значения ее потомков.

структура данных для хранения сортирующего дерева

Удобная структура данных для сортирующего дерева — такой массив Array, что Array[1] — элемент в корне, а потомки элемента Array[i] — Array[2i] и Array[2i+1].

Рассматривая кучу как дерево, определим 'высоту' ее узла как число ребер в самом длинном нисходящем простом пути от этого узла к какому-то из листьев дерева. Высота кучи есть высота ее корневого узла. Высота кучи равна $\Theta \left( \log{n} \right)$.

Базовые процедуры

В этом разделе представлены основные базовые процедуры для работы с кучей.

Heapify

Процедура Heapify служит для поддержки свойства кучи и выполняется за время $O \left( \log{n} \right)$.

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

Эта процедура предназначена для создания кучи из неупорядоченного массива входных данных. Время работы равно $\Theta \left( n\log{n} \right)$.

Build_Heap(A)
	heap_size[A] <- length[A]
	for i <- floor(length[A] / 2) downto 1
		do Heapify(A, i)

Heapsort

Процедура Heapsort сортирует массив без привлечения дополнительной памяти за время $\Theta \left( n\log{n} \right)$.

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

Выполняет изменение элемента в куче за время $O \left( \log{n} \right)$.

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

Выполняет вставку в кучу за время $O \left( \log{n} \right)$.

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

Выполняет извлечение из кучи за время $O \left( \log{n} \right)$.

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