Структуры данных. Куча

Это краткий дополненный конспект части о кучах в книге Гид по Computer Science, Вильям Спрингер.

Основная информация

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

При каждой операции сортирует себя, чтобы все уровни дерева (кроме последнего) были заполнены.

Куча частично упорядочена по ключам - элемент с наивысшим (или низшим) приоритетом в корне кучи.

Как правило, реализуются на основе массивов. Как и в стеке, в куче можно удалить за один раз только один элемент. Только это не последний добавленный, а наибольший (для max-кучи) или наименьший элемент (для min-кучи).

Пример max-кучи:

Узлы-братья (с одним и тем же родителем) с друг-другом не связаны. Они имеют более низкий приоритет чем их родители.

Неубывания (min-куча) - значение каждого узла больше, чем у его родителя.

Поддерживает операции:

поиска максимального значения (find-max) (peek),
вставки (insert) (push),
извлечения максимального значения (extract-max) (pop),
увеличения ключа (increase-key) (изменения ключа узла с последующим перемещением узла на новое место на графе)

Невозрастания (max-куча) - значение каждого узла меньше, чем у родителя.

Если не указано иное - то мы имеем ввиду двоичную кучу - полное двоичное дерево, которое удовлетворяет свойству упорядоченности кучи.

Для двоичной кучи, после создания кучи из списка элементов за время O(n), каждая из этих операций занимает время O(lg n).

Также есть левосторонние кучи, биномиальные кучи и кучи Фибоначчи.

Используются в тех случаях, когда нужен быстрый доступ к наибольшему (или наименьшему) элементу списка без необходимости сортировки остальной части списка. Используются для реализации очередей с приоритетом: нас интересует не относительный порядок всех элементов, а только то, какой элемент является следующим в очереди, — это всегда текущий корень кучи.

Реализация кучи

Вершины начинают нумероваться с корня. Затем слева направо на каждом уровне.

Корень - вершина 0,

Его левый потомок - вершина 1,

правый потомок - вершина 2,

Самый левый внук корня - вершина 3 и т.д.

В этом примере узлы с 5-го по 9-й являются корнями кучи размером 1. Так, любой элемент в позиции от Math.floor(n/2) до n -1 кучи размером n - корень кучи размером 1.

Для любого узла k номер его родителя - Math.floor((k – 1)/2), дочерние элементы (если они есть) - имеют номера 2k + 1 и 2k + 2.

Чтобы эффективно определить позицию родительского или дочернего узла нужно выполнить умножение посредством сдвига битов; Получим положение нужного узла, если куча реализована на основе массива.

Куча строится рекурсивно. Строятся маленькие кучи и объединяются в большие.

Пример построения кучи взят с этого сайта:
В примере ниже построение min-кучи - наименьший элемент всегда в корне кучи. Чтобы построить max-кучу нужно использовать функцию компаратор constcomparator= (a, b) =>b - a;

Создадим класс Heap и зададим ему вспомогательные методы.

JavaScript

1const comparator = (a, b) => a - b;
2
3class Heap {
4	constructor(comparator) {
5		this.arr = [];
6		this.comparator = comparator;
7	}
8
9	isCorrectOrder(first, second) {
10		return this.comparator(first, second) < 0;
11	}
12
13	getLeftChildIndex(parentIndex) {
14		return 2 * parentIndex + 1;
15	}
16
17	getRightChildIndex(parentIndex) {
18		return 2 * parentIndex + 2;
19	}
20
21	getParentIndex(childIndex) {
22		return Math.floor((childIndex - 1) / 2);
23	}
24
25	leftChild(parentIndex) {
26		return this.arr[this.getLeftChildIndex(parentIndex)];
27	}
28
29	rightChild(parentIndex) {
30		return this.arr[this.getRightChildIndex(parentIndex)];
31	}
32
33	parent(childIndex) {
34		return this.arr[this.getParentIndex(childIndex)];
35	}
36
37	hasParent(childIndex) {
38		return this.getParentIndex(childIndex) >= 0;
39	}
40
41	hasLeftChild(parentIndex) {
42		return this.getLeftChildIndex(parentIndex) < this.arr.length;
43	}
44
45	hasRightChild(parentIndex) {
46		return this.getRightChildIndex(parentIndex) < this.arr.length;
47	}
48
49	isEmpty() {
50		return !this.arr.length;
51	}
52}

Добавление элемента

Новый элемент попадает в первую пустую ячейку массива. Если новый элемент меньше родительского (для min-кучи), то поднимаем его вверх рекурсивно, меняя местами с родителем, до тех пор пока он не окажется больше или не станет корнем кучи.

Максимальная высота дерева равна O(lg n), каждое сравнение/обмен занимает время O(1). Итого общее время вставки O(lg n).

JavaScript

1const comparator = (a, b) => a - b;
2
3class Heap {
4    // ...
5	push(item) {
6		this.arr.push(item);
7		this.heapifyUp();
8		return this;
9	}
10
11	heapifyUp(startIndex) {
12		let currentIndex = startIndex || this.arr.length - 1;
13
14		// Пока у элемента есть родитель  и пока элемент меньше родителя
15		// меняем элемент местами с родителем.
16		while (
17			this.hasParent(currentIndex) &&
18			!this.isCorrectOrder(
19				this.parent(currentIndex),
20				this.arr[currentIndex]
21			)
22		) {
23			let parentIndex = this.getParentIndex(currentIndex);
24			this.swap(currentIndex, parentIndex);
25			currentIndex = parentIndex;
26		}
27	}
28
29	swap(indexOne, indexTwo) {
30		const tmp = this.arr[indexTwo];
31		this.arr[indexTwo] = this.arr[indexOne];
32		this.arr[indexOne] = tmp;
33	}
34}
35
36const heap = new Heap(comparator);
37
38heap.push(14);
39heap.push(18);
40heap.push(4);
41heap.push(29);
42heap.push(18);
43heap.push(44);
44heap.push(3);
45console.log(heap);
46//[3, 18,  4, 29, 18, 44, 14]

Удаление корня из кучи

При удалении корня кучи остается пустое место, которое заменяем последним элементом (с самого низкого уровня кучи), при необходимости оставляя почти полное дерево. Затем поднимаем новый корень вверх, заменяя дочерними узлами с меньшими значениями, пока дерево снова не приобретет свойство кучи.

JavaScript

1class Heap {
2    //...
3	pop() {
4		if (this.arr.length === 0) {
5			return null;
6		}
7
8		if (this.arr.length === 1) {
9			return this.arr.pop();
10		}
11
12		const item = this.arr[0];
13
14		this.arr[0] = this.arr.pop();
15		this.heapifyDown();
16
17		return item;
18	}
19
20	heapifyDown(customStartIndex = 0) {
21		let currentIndex = customStartIndex;
22		let nextIndex = null;
23
24		while (this.hasLeftChild(currentIndex)) {
25			if (
26				this.hasRightChild(currentIndex) &&
27				this.isCorrectOrder(
28					this.rightChild(currentIndex),
29					this.leftChild(currentIndex)
30				)
31			) {
32				nextIndex = this.getRightChildIndex(currentIndex);
33			} else {
34				nextIndex = this.getLeftChildIndex(currentIndex);
35			}
36
37			if (
38				this.isCorrectOrder(this.arr[currentIndex], this.arr[nextIndex])
39			) {
40				break;
41			}
42
43			this.swap(currentIndex, nextIndex);
44			currentIndex = nextIndex;
45		}
46	}
47}
48
49//[3, 18,  4, 29, 18, 44, 14]
50heapArr.pop(3);
51// [ 4, 18, 14, 29, 18, 44 ]

Преобразование массива в кучу

Записываем получаемый массив в массив кучи и для каждого элемента вызываем метод heapifyUp.

JavaScript

1class Heap {
2   //...
3	buildHeap(array) {
4		this.arr = array;
5		let i = array.length - 1;
6		while (i > 1) {
7			this.heapifyUp(i)
8			i--;
9		}
10	}
11}
12
13const heap = new Heap(comparator);
14const arr = [24, 19, 2, 13, 101, 8];
15
16heap.buildHeap(arr);
17// [ 2, 24, 13, 19, 101, 8 ]

Полный код

JavaScript

1const comparator = (a, b) => a - b;
2
3class Heap {
4	constructor(comparator) {
5		this.arr = [];
6		this.comparator = comparator;
7	}
8
9	isCorrectOrder(first, second) {
10		return this.comparator(first, second) < 0;
11	}
12
13	getLeftChildIndex(parentIndex) {
14		return 2 * parentIndex + 1;
15	}
16
17	getRightChildIndex(parentIndex) {
18		return 2 * parentIndex + 2;
19	}
20
21	getParentIndex(childIndex) {
22		return Math.floor((childIndex - 1) / 2);
23	}
24
25	leftChild(parentIndex) {
26		return this.arr[this.getLeftChildIndex(parentIndex)];
27	}
28
29	rightChild(parentIndex) {
30		return this.arr[this.getRightChildIndex(parentIndex)];
31	}
32
33	parent(childIndex) {
34		return this.arr[this.getParentIndex(childIndex)];
35	}
36
37	hasParent(childIndex) {
38		return this.getParentIndex(childIndex) >= 0;
39	}
40
41	hasLeftChild(parentIndex) {
42		return this.getLeftChildIndex(parentIndex) < this.arr.length;
43	}
44
45	hasRightChild(parentIndex) {
46		return this.getRightChildIndex(parentIndex) < this.arr.length;
47	}
48
49	isEmpty() {
50		return !this.arr.length;
51	}
52
53	buildHeap(array) {
54		this.arr = array;
55		let i = array.length - 1;
56		while (i > 1) {
57			this.heapifyUp(i)
58			i--;
59		}
60	}
61
62	push(item) {
63		this.arr.push(item);
64		this.heapifyUp();
65		return this;
66	}
67
68	heapifyUp(startIndex) {
69		let currentIndex = startIndex || this.arr.length - 1;
70
71		// Пока у элемента есть родитель  и пока элемент меньше родителя
72		// меняем элемент местами с родителем.
73		while (
74			this.hasParent(currentIndex) &&
75			!this.isCorrectOrder(
76				this.parent(currentIndex),
77				this.arr[currentIndex]
78			)
79		) {
80			let parentIndex = this.getParentIndex(currentIndex);
81			this.swap(currentIndex, parentIndex);
82			currentIndex = parentIndex;
83		}
84	}
85
86	swap(indexOne, indexTwo) {
87		const tmp = this.arr[indexTwo];
88		this.arr[indexTwo] = this.arr[indexOne];
89		this.arr[indexOne] = tmp;
90	}
91
92	pop() {
93		if (this.arr.length === 0) {
94			return null;
95		}
96
97		if (this.arr.length === 1) {
98			return this.arr.pop();
99		}
100
101		const item = this.arr[0];
102
103		this.arr[0] = this.arr.pop();
104		this.heapifyDown();
105
106		return item;
107	}
108
109	heapifyDown(customStartIndex = 0) {
110		let currentIndex = customStartIndex;
111		let nextIndex = null;
112
113		while (this.hasLeftChild(currentIndex)) {
114			if (
115				this.hasRightChild(currentIndex) &&
116				this.isCorrectOrder(
117					this.rightChild(currentIndex),
118					this.leftChild(currentIndex)
119				)
120			) {
121				nextIndex = this.getRightChildIndex(currentIndex);
122			} else {
123				nextIndex = this.getLeftChildIndex(currentIndex);
124			}
125
126			if (
127				this.isCorrectOrder(this.arr[currentIndex], this.arr[nextIndex])
128			) {
129				break;
130			}
131
132			this.swap(currentIndex, nextIndex);
133			currentIndex = nextIndex;
134		}
135	}
136}

Другие посты

Ничего не найдено