Структурите на данни са важни в компютърното програмиране за организиране, управление и съхраняване на данни по бърз и ефективен начин. Структурите на данни са абсолютно важно умение, което всеки разработчик трябва да има в своя инструментариум.
Днес ще продължим с поредицата Data Structures 101, като се фокусираме върху Heaps, специална дървовидна структура от данни, която реализира цялостно двоично дърво.
Днес ще разгледаме:
- Какво е Heap?
- Основни операции в купчини
- Как да изградите Max Heap
- Как да изградите Min Heap
- Купища предизвикателство: практическа практика
- Какво да научите след това
Какво е Heap?
Купчината е усъвършенствана дървовидна структура от данни, използвана предимно за сортиране и прилагане на приоритетни „опашки“. Те са пълни двоични дървета, които имат следните характеристики:
- Всяко ниво е запълнено с изключение на листовите възли (възлите без деца се наричат листа).
- Всеки възел има максимум 2 деца.
- Всички възли са възможно най-отляво. Това означава, че всяко дете е отляво на своя родител.
Груповете използват пълни двоични дървета, за да избегнат дупки в масива. Пълно двоично дърво е дърво, при което всеки възел има най-много две деца и възлите на всички нива са пълни, с изключение на листовите възли, които могат да бъдат празни. Купчините се изграждат въз основа на свойството heap, което сравнява ключа на родителския възел с ключовете на дъщерния възел.
Важно е да се отбележи, че купчините не винаги са сортирани. Ключовото условие, което следват, е най-големият или най-малкият елемент да бъде поставен върху основния възел (отгоре) в зависимост от това дали е Max или Min Heap. Heap структурата на данните не е същата като heap паметта.
Плюсове и минуси на Heaps
Плюсове:
- Събирането на боклука се изпълнява в паметта на стека, за да се освободи паметта, използвана от обекта.
- Купчините са гъвкави, тъй като паметта може да бъде разпределена или премахната в произволен ред.
- Променливите могат да бъдат достъпни глобално.
- Помага да се намери минималното и най-голямото число.
Недостатъци:
- В сравнение със стековете, купчините отнемат повече време за изпълнение.
- Управлението на паметта е по-сложно в heap паметта, тъй като се използва глобално.
- Купчините обикновено отнемат повече време за изчисляване.
Приложения на Heap структура от данни
Купчините са ефикасни за намиране на минималния или максималния елемент в масив и са полезни в статистиката на поръчките и алгоритмите за избор. Времевата сложност за получаване на минималната/максималната стойност от куп е O(1), (постоянна времева сложност).
Приоритетните опашки са проектирани въз основа на структури на купчина. Отнема O(log(n)) време за ефективно вмъкване (insert()) и изтриване (delete()) на всеки елемент в опашката с приоритети.
Приоритетните опашки, внедрени в купчина, се използват в популярни алгоритми като:
- Алгоритъмът на Prim
- Алгоритъмът на Дейкстра
- Heapsort алгоритъм
Основни операции в купчини
По-долу са основните операции, които можете да използвате, когато внедрявате структура от данни в купчина:
heapify: пренарежда елементите в купчината, за да поддържа свойството на купчината.insert: добавя елемент към купчина, като същевременно запазва свойството си за купчина.delete: премахва елемент в купчина.extract: връща стойността на елемент и след това го изтрива от купчината.isEmpty: boolean, връща true, ако boolean е празен, и false, ако има възел.size: връща размера на купчината.getMax(): връща максималната стойност в куп
Как да изградите максимална купчина
Елементите в max heap следват свойството max heap. Това означава, че ключът в родителския възел винаги е по-голям от ключа в двата дъщерни възела. За да изградите максимален куп:
- Създайте нов възел в началото (корена) на купчината.
- Задайте му стойност.
- Сравнете стойността на дъщерния възел с родителския възел.
- Разменете възли, ако стойността на родителя е по-малка от тази на което и да е дете (отляво или отдясно).
- Повторете, докато най-големият елемент е в главните родителски възли (тогава можете да кажете, че свойството на купчината е валидно).
Тези стъпки могат да се следват и при вмъкване на нови елементи в куп. Ключът тук е каквато и операция да се извършва върху Max Heap, свойството на heap трябва да се поддържа.
За да премахнете/изтриете основен възел в Max Heap:
- Изтрийте основния възел.
- Преместете последния дъщерен възел на последното ниво в корена.
- Сравнете родителския възел с неговите деца.
- Ако стойността на родителя е по-малка от дъщерните възли, разменете ги и повторете, докато свойството на купчината бъде удовлетворено.
Нека да разгледаме как изглежда това в код. В следващия раздел ще внедрим максимална купчина с помощта на JavaScript.
Внедряване на Max Heap в JavaScript
Преди да започнем да създаваме Max Heap, разгледайте някои от методите, които ще приложим и какво правят:
_percolateUp(): възстановява свойството на купчина от дъщерен възел към основен възел._maxHeapify(): възстановява свойството на купчина от конкретен възел надолу до листови възли.insert(): добавя дадена стойност към масива на купчината и пренарежда елементите въз основа на тяхното свойство на купчината. При всяко ново вмъкване купчината нараства равномерно и размерът се увеличава с единица.getMax(): връща максималната стойност в купчината (основен възел), без да променя купчината. Имайте предвид, че времевата сложност тук е постоянно време O(1)removeMax(): връща и премахва максималната стойност в купчината (мислете заpop()). Времевата сложност на тази функция е в O(log(n)).
Ако размерът на купчината е по-голям от едно, той съхранява максималната стойност в променлива, разменя тази стойност с последния лист и изтрива максималната стойност от купчината.
Ако купчината има само един елемент, тя изтрива и връща стойността на този елемент, последното условие е, ако купчината е празна, връща нула.
Методът __percolateUp() се извиква рекурсивно на всеки родителски възел, докато се достигне коренът. За всеки възел, който трябва да бъде позициониран след свойството max-heap, ние извикваме метода __maxHeapify() при всеки индекс на този масив, започвайки от дъното на купчината.
class maxHeap {
constructor() {
this.heap = [];
this.elements = 0;
};
insert(val) {
if (this.elements >= this.heap.length) {
this.elements = this.elements + 1;
this.heap.push(val);
this.__percolateUp(this.heap.length - 1);
}
else {
this.heap[this.elements] = val;
this.elements = this.elements + 1;
this.__percolateUp(this.elements - 1);
}
};
getMax() {
if (this.elements !== 0)
return this.heap[0];
return null;
};
removeMax() {
let max = this.heap[0];
if (this.elements > 1) {
this.heap[0] = this.heap[this.elements - 1];
this.elements = this.elements - 1;
this.__maxHeapify(0);
return max
} else if (this.elements === 1) {
this.elements = this.elements - 1;
return max;
} else {
return null;
}
};
__percolateUp(index) {
const parent = Math.floor((index - 1) / 2);
if (index <= 0)
return
else if (this.heap[parent] < this.heap[index]) {
let tmp = this.heap[parent];
this.heap[parent] = this.heap[index];
this.heap[index] = tmp;
this.__percolateUp(parent);
}
};
__maxHeapify(index) {
let left = (index * 2) + 1;
let right = (index * 2) + 2;
let largest = index;
if ((this.elements > left) && (this.heap[largest] < this.heap[left])) {
largest = left
}
else if ((this.elements > right) && (this.heap[largest] < this.heap[right]))
largest = right
else if (largest !== index) {
const tmp = this.heap[largest];
this.heap[largest] = this.heap[index];
this.heap[index] = tmp;
this.__maxHeapify(largest);
}
};
buildHeap(arr) {
this.heap = arr;
this.elements = this.heap.length;
for (let i = this.heap.length - 1; i >= 0; i--) {
this.__maxHeapify(i);
}
};
};
let heap = new maxHeap();
Как да изградите min Heap
Интуитивно можем да кажем, че елементите в min heap следват свойството min heap, тъй като това е противоположно на max heaps. Ключът в родителския възел винаги е по-малък от ключа в двата дъщерни възела. За да създадете min heap:
- Създайте нов дъщерен възел в края на купчината (последно ниво).
- Добавете новия ключ към този възел (добавете го към масива).
- Преместете дъщерния елемент нагоре, докато стигнете до коренния възел и свойството на купчината е изпълнено.
За да премахнете/изтриете основен възел в min heap:
- Изтрийте основния възел.
- Преместете ключа на последното дете към корена.
- Сравнете родителския възел с неговите деца.
- Ако стойността на родителя е по-голяма от дъщерните възли, разменете ги и повторете, докато свойството на купчината бъде удовлетворено.
Внедряване на Min Heap в JavaScript
Преди да навлезем в изграждането на min heap, имайте предвид, че неговата реализация е подобна на тази на Max Heap. minHeapify() възстановява свойството heap. getMin() връща минималната стойност в купчината (основен възел), без да променя купчината. А removeMin() изтрива минималната стойност и я връща.
class minHeap {
constructor() {
this.heap = []
this.elements = 0;
};
insert(val) {
if (this.elements >== this.heap.length) {
this.elements = this.elements + 1
this.heap.push(val);
this.__percolateUp(this.heap.length - 1);
}
else {
this.heap[this.elements] = val;
this.elements = this.elements + 1;
this.__percolateUp(this.elements - 1);
}
};
getMin() {
if (this.heap.length !== 0)
return this.heap[0];
return null;
}
removeMin() {
const min = this.heap[0];
if (this.elements > 1) {
this.heap[0] = this.heap[this.elements - 1];
this.elements = this.elements - 1;
this.__minHeapify(0);
return min;
} else if (this.elements == 1) {
this.elements = this.elements - 1;
return min;
} else {
return null;
}
};
__percolateUp(index) {
let parent = Math.floor((index - 1) / 2);
if (index <= 0)
return
else if (this.heap[parent] > this.heap[index]) {
let tmp = this.heap[parent];
this.heap[parent] = this.heap[index];
this.heap[index] = tmp;
this.__percolateUp(parent);
}
};
__minHeapify(index) {
let left = (index * 2) + 1;
let right = (index * 2) + 2;
let smallest = index;
if ((this.elements > left) && (this.heap[smallest] > this.heap[left])) {
smallest = left;
}
if ((this.elements > right) && (this.heap[smallest] > this.heap[right]))
smallest = right;
if (smallest !== index) {
let tmp = this.heap[smallest];
this.heap[smallest] = this.heap[index];
this.heap[index] = tmp;
this.__minHeapify(smallest);
}
}
buildHeap(arr) {
this.heap = arr;
this.elements = this.heap.length;
for (let i = this.heap.length - 1; i >= 0; i--) {
this.__minHeapify(i)
}
}
};
let heap = new minHeap();
heap.insert(12);
heap.insert(10);
heap.insert(-10);
heap.insert(100);
console.log(heap.getMin()); //you should get -10
let newheap = new minHeap();
let arr = [12, 6, 8, 3, 16, 4, 27];
newheap.buildHeap(arr) //builds this new heap with elements from the array
console.log(newheap.getMin()) //this logs 3
newheap.removeMin();
console.log(newheap.getMin())
Heaps Challenge: Преобразувайте Max Heap в Min Heap
Нека направим нашето учене една крачка напред с практическо предизвикателство. Нашата цел тук е да преобразуваме максимална купчина в минимална купчина. Следвайте нашето кодово решение, за да видите как се прави.
Изявление на проблема: Приложете функция convertMax(maxHeap), която ще преобразува двоичен максимален обем в двоичен минимум, където maxHeap е масив във формат maxHeap (т.е. родителят е по-голям от своите деца). Вашият резултат трябва да бъде преобразуван масив.
Примерно въвеждане:
maxHeap = [9,4,7,1,-2,6,5]
Примерен резултат:
result = [-2,1,5,9,4,6,7]
Проблем:
function convertMax(maxHeap) {
return maxHeap
}
Решение:
function minHeapify(heap, index) {
var left = index * 2;
var right = (index * 2) + 1;
var smallest = index;
if ((heap.length > left) && (heap[smallest] > heap[left])) {
smallest = left
}
if ((heap.length > right) && (heap[smallest] > heap[right]))
smallest = right
if (smallest != index) {
var tmp = heap[smallest]
heap[smallest] = heap[index]
heap[index] = tmp
minHeapify(heap, smallest)
}
return heap;
}
function convertMax(maxHeap) {
for (var i = Math.floor((maxHeap.length) / 2); i > -1; i--)
maxHeap = minHeapify(maxHeap, i)
return maxHeap
}
Кодовото решение по-горе може да се изпълни. Можем да считаме дадения maxHeap за нормален масив от елементи и да го пренаредим така, че да представлява точно min heap. Функцията convertMax() възстановява свойството на купчината на всички възли от най-ниския родителски възел, като извиква функцията minHeapify() на всеки.
Времевата сложност на изграждането на куп еO(n). Това важи и за този проблем.
function minHeapify(heap, index) {
var left = index * 2;
var right = (index * 2) + 1;
var smallest = index;
if ((heap.length > left) && (heap[smallest] > heap[left])) {
smallest = left
}
if ((heap.length > right) && (heap[smallest] > heap[right]))
smallest = right
if (smallest != index) {
var tmp = heap[smallest]
heap[smallest] = heap[index]
heap[index] = tmp
minHeapify(heap, smallest)
}
return heap;
}
function convertMax(maxHeap) {
for (var i = Math.floor((maxHeap.length) / 2); i > -1; i--)
maxHeap = minHeapify(maxHeap, i)
return maxHeap
}
var maxHeap = [9,4,7,1,-2,6,5]
console.log(convertMax(maxHeap))
-->
[ -2, 1, 4, 5, 7, 6, 9 ]
Какво да научите след това
Поздравления, че стигнахте до края на тази статия. Надявам се, че вече имате добри познания за това как работят купчините и можете уверено да изградите купчина с JavaScript.
Ето някои често срещани предизвикателства, които биха ви помогнали да проверите знанията си за структурата на данните в купчина. Можете да очаквате да видите тези въпроси в интервю за кодиране:
- Преобразувайте Max Heap в Min Heap
- Намерете k най-малък елемент в масив
- Намерете k най-големия елемент в масив
- Проверете дали даден масив представлява min heap или не
- Обединете M-сортирани списъци с променлива дължина
- Намерете най-малкия диапазон с поне един елемент от всеки от дадените списъци
За да намерите отговори на тези въпроси и да продължите обучението си, вижте курса на Educative Структури на данни за интервюта за кодиране в JavaScript. Той ще ви даде подробно обяснение на всички често срещани структури от данни на JavaScript с решения на реални проблеми със структурата на данни. Ще станете добре оборудвани с всички различни структури от данни, които използвате, за да напишете по-добър код.
Приятно учене!
Продължете да четете за JavaScript и структурите от данни в Educative
- Върхови структури от данни и алгоритми, които всеки разработчик трябва да знае
- Урок за игра на JavaScript Snake: създаване на проста, интерактивна игра
- Шпаргалка за нотация Big-O: бързи отговори на въпроси за Big-O
Започнете дискусия
Коя е любимата ви структура от данни на JavaScript за работа? Беше ли полезна тази статия? Кажете ни в коментарите по-долу!
