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

Материал из Википедии — свободной энциклопедии

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

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

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

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

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

Удобная структура данных для сортирующего дерева — такой массив 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)

Процедура добавления элемента в кучу на языке Pascal

procedure add(x:integer);
begin
  inc(size);{size-текущее число элементов}
  heap[size]:=x;{heap[]-элемент кучи}
  i:=size;
  while (i>1) do
    begin
      if (heap[i div 2]>heap[i]) then
        begin
          swap(heap[i],heap[i div 2]);{swap-процедура перестановки элементов}
          i:=i div 2;
        end else break;
    end;
end;

[править] 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