Куча — это полное бинарное дерево (каждый корень имеет максимальное количество доступных значений). Полное бинарное дерево — это бинарное дерево, в котором все уровни полностью заполнены, за исключением, возможно, самого нижнего уровня, который заполняется слева. Бинарное дерево состоит из 2**(h+1) -1 узлов (h — высота бинарного дерева).
Есть два типа кучи:
- Максимальная куча
- Минимальная куча
Максимальная куча:Максимальная куча — это полное двоичное дерево, в котором каждый узел (элемент) имеет значение, большее или равное его дочерним узлам (потомкам).
Минимальная куча. Минимальная куча — это полное двоичное дерево, в котором каждый узел (элемент) имеет значение, меньшее или равное его дочерним узлам (потомкам).
Представление в виде массива минимальной кучи: [1,3,2,4,6,5] и максимальной кучи: [6,5,3,4,2,1]
Для объяснения давайте использовать Max heap и array[6,5,3,4,2,1].
Есть несколько вещей, которые нам нужно понять, прежде чем мы приступим к кодированию.
- Как найти родителя элемента?
- Как найти левого дочернего элемента элемента?
- Как найти правильный дочерний элемент элемента?
- Является ли текущий узел конечным узлом (конечный узел – это узел, не имеющий дочерних элементов)?
Родитель элемента.Чтобы найти родителя элемента, используйте формулу. Math.floor((index-1)/2). давайте предположим, что нам нужно найти родителя элемента 4, который в настоящее время имеет индекс 4.
const parent = Math.floor((index-1)/2);// that is Math.floor(4-1)/2 = 1(index of parent), // which is 5. so 5 is the parent of 4.
Левый дочерний элемент элемента. Чтобы найти левого дочернего элемента элемента, используйте формулу (2*index)+1. Предположим, нам нужно найти левого дочернего элемента 5 с индексом 1.
const leftChild = (2*index)+1; // that is (2*1)+1 = 3(index of left child) // according to this 4 which is at index 3 is the left child of 5.
Правый дочерний элемент. Чтобы найти правый дочерний элемент элемента, используйте формулу (2*index)+2. Предположим, нам нужно найти правильный дочерний элемент 5 с индексом 1.
const rightChild = (2*index)+2; // that is (2*1)+2 = 4(index of right child) // according to this 2 which is at index 4 is the right child of 3.
Проверка того, является ли текущий узел листовым узлом:Чтобы проверить, является ли текущий индекс листовым узлом, нам нужно проверить, превышает ли текущий индекс половину длины массива и меньше длины массива. Это означает, что дочерних узлов нет.
//so we can check through
const leftChild = index >= Math.floor(this.value.length / 2) &&
index <= this.value.length - 1
«В этом блоге мы также рассмотрим несколько концепций»
- Вставка
- Удаление
- Увеличить
- И, наконец, работа над сортировкой кучи
Вставка
Предположим, у нас есть представление массива max heap, равное [6,5,3,4,2,1], и мы хотим вставить новый элемент в кучу , тогда нам нужно поместить элемент в массив и проверить с его родителем, удовлетворяет ли условие для максимальной кучи или нет (в основном, если родитель больше или равен дочернему элементу или нет.). если текущий узел не удовлетворяет условию, нам нужно поменять их местами и проверить наличие нового узла.
Вставка следует подходу кучи вверх, поскольку мы проверяем от листа к корню.
Временная сложность вставки:Количество обменов, происходящих во время вставки, может быть максимальным до высоты дерева, т.е. (log n), поэтому время сложности в наихудшем случае вставки — O(log n).
Удаление
В нашем массиве [6,5,3,4,2,1], если вы хотите удалить элемент, это должен быть корень element, поэтому в нашем случае корень равен 6. Как только мы удалим 6, последний элемент в массиве (т.е. - 1) займет место корневого элемента. Как только это будет сделано, нам нужно настроить дерево и сравнить левый и дочерний узел с новым корневым элементом, если текущая куча удовлетворяет свойствам максимальной кучи или нет. если нет, то нам нужно поменять их местами.
Удаление следует подходу heapify Down, поскольку мы сравниваем от корня к листу.
Временная сложность удаления:количество обменов, происходящих во время удаления, может быть максимальным до высоты дерева, т.е. (log n), поэтому временная сложность в наихудшем случае вставки — O(log n).
Нагромождение
Heapify — это процесс создания структуры данных кучи из двоичного дерева, представленного с помощью массива. Как только мы удаляем или добавляем элемент в кучу, нам нужно выполнить heapifyUp (после добавления) и heapifyDown (после удаления).
HeapifyUp означает обработку элементов в куче от листа до корня и обработку того, находятся ли элементы в порядке и удовлетворяют ли они максимальной куче или нет, если нет, нам нужно их поменять местами.
HeapifyDown означает обработку элементов в куче от корня к листу и обработку того, находятся ли элементы в порядке и удовлетворяют ли они максимальной куче или нет, если нет, нам нужно их поменять местами.
Heapify имеет временную сложность O(n).
Куча сортировки
Сортировка кучей в основном представляет собой концепцию сначала создания кучи, а затем удаления кучи и построения отсортированного массива. По мере удаления мы получаем максимальный элемент из доступного массива. Итак, мы рассмотрим работу обоих этих процессов.
- Построить кучу.
- Удалить элемент из кучи.
Предположим, у нас есть исходный массив [10,20,15,30,40]
Давайте рассмотрим несколько важных функций, которые мы собираемся использовать для нашей сортировки в куче.
- Чтобы найти родителя элемента по индексу
// to fetch parent of the node
// the formulae is (index - 1 /2)
parent(index) {
return Math.floor((index - 1) / 2);
}
- Чтобы найти индекс левого узла
// fetch index of left node from index of parent node
leftNode(index) {
return 2 * index + 1;
}
- Чтобы найти индекс правого узла
// fetch index of right node from index of parent node
rightNode(index) {
return 2 * index + 2;
}
- Чтобы определить, является ли текущий узел конечным узлом или нет
//if the index is more than the half of length of array and index is less than length of array, means,
//there is no child node
isLeaf(index) {
return (
index >= Math.floor(this.value.length / 2) &&
index <= this.value.length - 1
);
}
- поменять местами два значения
// swap functionality
swap(index, target) {
[this.value[index], this.value[target]] = [
this.value[target],
this.value[index],
];
}
- Чтобы выполнить heapifyUp
// this will check each node and compare if the current node is at right path or not while comparing it with its parent
// this is a leaf to root approach
heapifyUp(index) {
let currentNodeIndex = index;
let parentNodeIndex = this.parent(currentNodeIndex);
// we need to perform while loop until we reach the top node and value of child is more than parent node
while (
parentNodeIndex >= 0 &&
currentNodeIndex > 0 &&
this.value[currentNodeIndex] > this.value[parentNodeIndex]
) {
// current child is greater than parent so we need to swap them
this.swap(currentNodeIndex, parentNodeIndex);
// now we need to set the current parent as child and find the new parent for the child node
currentNodeIndex = parentNodeIndex;
parentNodeIndex = this.parent(parentNodeIndex);
}
}
- Чтобы выполнить HeapifyDown
// if we remove an element from the heap , we need to perform heapifyDown
// so that we compare if the nodes are at right position
// this is root to leaf approach, there we compare the childrens with the current node
heapifyDown(index) {
// we need to check if current node is not a leaf
if (!this.isLeaf(0)) {
// fetch left node
let leftNode = this.leftNode(index);
// fetch right node
let rightNode = this.rightNode(index);
let biggerNode = index;
// we need to compare if the left and right node are bigger or not
if (this.value[biggerNode] < this.value[leftNode]) {
biggerNode = leftNode;
}
if (this.value[biggerNode] < this.value[rightNode]) {
biggerNode = rightNode;
}
// checking if we have any mismatch, if yes swap
if (biggerNode != index) {
this.swap(index, biggerNode);
this.heapifyDown(biggerNode);
}
}
}
- Чтобы извлечь максимальный элемент из кучи
// method to fetch the top element from the heap
extractMax() {
if (!this.value.length) return;
// fetch the largest value
const largestValue = this.value[0];
// replace with last node
this.value[0] = this.value.pop();
// once we remove the top element, we need to perform heapifyDown to take the elements to its right place in heap
this.heapifyDown(0);
return largestValue;
}
- Создать кучу из предоставленного массива
// build an heap from the array
buildHeap(heapNodes) {
this.value = heapNodes;
for (let i = Math.floor(this.value.length / 2); i >= 0; i--) {
// we need to perform heapifyDown to put elements to its right place
this.heapifyDown(i);
}
}
Давайте перейдем к работе с сортировкой кучи, объединив все доступные функции.
мы будем использовать классы javascript для построения этого алгоритма. Ниже приведена сортировка кучей в коде.
class HeapSort {
constructor() {
this.value = []; // store the nodes
}
// to fetch parent of the node
// the formulae is (index -1 /2)
parent(index) {
return Math.floor((index - 1) / 2);
}
// fetch index of left node from index of parent node
leftNode(index) {
return 2 * index + 1;
}
// fetch index of right node from index of parent node
rightNode(index) {
return 2 * index + 2;
}
//if the index is more than the half of length of array and index is less than length of array, means,
//there is no child node
isLeaf(index) {
return (
index >= Math.floor(this.value.length / 2) &&
index <= this.value.length - 1
);
}
// swap functionality to swap nodes if conditions not meet
swap(index, target) {
[this.value[index], this.value[target]] = [
this.value[target],
this.value[index],
];
}
//Adding a node to the last of the array and then perform heapifyUp to put node at its right position
addNode(node) {
this.value.push(node);
//heapify up to put the node at right point
this.heapifyUp(this.value.length - 1);
}
// this will check each node and compare if the current node is at right path or not while comparing it with its parent
// this is a leaf to root approach
heapifyUp(index) {
let currentNodeIndex = index;
let parentNodeIndex = this.parent(currentNodeIndex);
// we need to perform while loop until we reach the top node and value of child is more than parent node
while (
parentNodeIndex >= 0 &&
currentNodeIndex > 0 &&
this.value[currentNodeIndex] > this.value[parentNodeIndex]
) {
// current child is greater than parent so we need to swap them
this.swap(currentNodeIndex, parentNodeIndex);
// now we need to set the current parent as child and find the new parent for the child node
currentNodeIndex = parentNodeIndex;
parentNodeIndex = this.parent(parentNodeIndex);
}
}
// if we remove an element from the heap , we need to perform heapifyDown
// so that we compare if the nodes are at right position
// this is root to leaf approach, there we compare the childrens with the current node
heapifyDown(index) {
// we need to check if current node is not a leaf
if (!this.isLeaf(0)) {
// fetch left node
let leftNode = this.leftNode(index);
// fetch right node
let rightNode = this.rightNode(index);
let biggerNode = index;
// we need to compare if the left and right node are bigger or not
if (this.value[biggerNode] < this.value[leftNode]) {
biggerNode = leftNode;
}
if (this.value[biggerNode] < this.value[rightNode]) {
biggerNode = rightNode;
}
// checking if we have any mismatch, if yes swap
if (biggerNode != index) {
this.swap(index, biggerNode);
this.heapifyDown(biggerNode);
}
}
}
// method to fetch the top element from the heap
extractMax() {
if (!this.value.length) return;
// fetch the largest value
const largestValue = this.value[0];
// replace with last node
this.value[0] = this.value.pop();
// once we remove the top element, we need to perform heapifyDown to take the elements to its right place in heap
this.heapifyDown(0);
return largestValue;
}
// build an heap from the array
buildHeap(heapNodes) {
this.value = heapNodes;
for (let i = Math.floor(this.value.length / 2); i >= 0; i--) {
// we need to perform heapifyDown to put elements to its right place
this.heapifyDown(i);
}
}
}
Вы можете протестировать работу, предоставив массив через функцию buildHeap.
const heap = new HeapSort(); heap.buildHeap([10,20,15,30,40]); console.log(heap.extractMax()); console.log(heap.extractMax()); console.log(heap.extractMax()); console.log(heap.extractMax()); console.log(heap.extractMax());
Ответ:
Вы можете протестировать, добавив узлы:
const heap = new HeapSort(); heap.addNode(10); heap.addNode(20); heap.addNode(15); heap.addNode(30); heap.addNode(40); console.log(heap.extractMax()); console.log(heap.extractMax()); console.log(heap.extractMax()); console.log(heap.extractMax()); console.log(heap.extractMax());
Ответ такой же, как и выше.
Я попытался прокомментировать каждую функциональную часть алгоритма в коде. если у вас все еще есть какие-либо проблемы с пониманием этого, оставьте комментарий, и я постараюсь ответить на ваши вопросы.
Следите за новостями. Если вы впервые здесь, загляните в наш блог Алгоритмы с использованием Javascript, в котором мы расскажем о нескольких наиболее часто используемых алгоритмах с использованием javascript.
В следующем блоге мы рассмотрим Поиск в ширину.
