Главная » Программирование и разработка

Структура данных 101: как создавать минимальную и максимальную heaps (кучу)

как создавать минимальную и максимальную heaps Программирование и разработка
На чтение 18 мин Просмотров 1.8к. Опубликовано

Структуры данных важны в компьютерном программировании для быстрой и эффективной организации, управления и хранения данных. Структуры данных — это абсолютно необходимый навык для любого разработчика, который должен быть в своем наборе инструментов.

Сегодня мы продолжим серию статей «Структура данных 101», сосредоточив внимание на кучах, специальной древовидной структуре данных, которая реализует полное двоичное дерево.

Содержание
  1. Что такое куча (heaps)?
  2. Плюсы и минусы Heaps
  3. Применение структуры данных кучи
  4. Основные операции в кучах
  5. Как создать максимальную кучу
  6. Чтобы удалить / удалить корневой узел в Max Heap, вы:
  7. Реализация максимальной кучи в JavaScript
  8. Как построить минимальную кучу
  9. Чтобы удалить / удалить корневой узел в минимальной куче:
  10. Реализация Min Heap в JavaScript
  11. Задача кучи: преобразование максимальной кучи в минимальную кучу

Что такое куча (heaps)?

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

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

Пример максимальной кучи

Пример максимальной кучи

В кучах используются полные двоичные деревья, чтобы избежать дыр в массиве. Полное двоичное дерево — это дерево, в котором каждый узел имеет не более двух дочерних элементов, а узлы на всех уровнях заполнены, за исключением конечных узлов, которые могут быть пустыми. Кучи строятся на основе свойства кучи, которое сравнивает ключ родительского узла с ключами его дочернего узла.

В более поздней части этой статьи мы подробно обсудим Min Heap, построенный на свойстве Min Heap, и Max Heap, построенный на свойстве Max Heap.

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

Читайте также:  Массивы в руководстве по Java: как объявлять и инициализировать массивы Java

Плюсы и минусы Heaps

Плюсы

  • Сборка мусора выполняется в памяти кучи, чтобы освободить память, используемую объектом.
  • Кучи гибки, поскольку память может выделяться или удаляться в любом порядке.
  • Доступ к переменным можно получить глобально.
  • Это помогает найти минимальное и максимальное количество.

Минусы

  • По сравнению со стеками, куча требует больше времени для выполнения.
  • В динамической памяти управление памятью сложнее, поскольку она используется глобально.
  • Обычно для вычисления кучи требуется больше времени.

Применение структуры данных кучи

Кучи эффективны для поиска минимального или максимального элемента в массиве и полезны в статистике порядка и алгоритмах выбора. Временная сложность получения минимального / максимального значения из кучи составляетО (1)О ( 1 ), (постоянная временная сложность).

Очереди с приоритетом разработаны на основе структур кучи. ЗанимаетO (журнал (n))O ( l o g ( n ) )время для эффективной вставки ( insert()) и удаления ( delete()) каждого элемента в приоритетной очереди.

Очереди приоритетов, реализованные в куче, используются в популярных алгоритмах, таких как:

  • Алгоритм Прима
  • Алгоритм Дейкстры
  • Алгоритм Heapsort

Основные операции в кучах

Ниже перечислены основные операции, которые вы можете использовать при реализации структуры данных кучи:

  • heapify: переупорядочивает элементы в куче, чтобы сохранить свойство кучи.
  • insert: добавляет элемент в кучу, сохраняя его свойство кучи.
  • delete: удаляет элемент из кучи.
  • extract: возвращает значение элемента и затем удаляет его из кучи.
  • isEmpty: boolean, возвращает true, если boolean пусто, и false, если есть узел.
  • size: возвращает размер кучи.
  • getMax(): возвращает максимальное значение в куче

Как создать максимальную кучу

Элементы в максимальной куче следуют свойству максимальной кучи. Это означает, что ключ на родительском узле всегда больше ключа на обоих дочерних узлах. Чтобы создать максимальную кучу, вы:

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

Эти шаги также можно выполнить при вставке новых элементов в кучу. Ключевым моментом здесь является то, что какая бы операция ни выполнялась с Max Heap, свойство кучи должно сохраняться.

Чтобы удалить / удалить корневой узел в Max Heap, вы:

  • Удалите корневой узел.
  • Переместите последний дочерний узел последнего уровня в корневой.
  • Сравните родительский узел с его дочерними узлами.
  • Если значение родительского узла меньше дочерних узлов, поменяйте их местами и повторяйте, пока свойство кучи не будет удовлетворено.

Давайте посмотрим, как это выглядит в коде. В следующем разделе мы реализуем максимальную кучу с помощью JavaScript.

Реализация максимальной кучи в JavaScript

Прежде чем мы перейдем к созданию Max Heap, взглянем на некоторые методы, которые мы реализуем, и на то, что они делают:

  • _percolateUp(): восстанавливает свойство кучи с дочернего узла на корневой узел.
  • _maxHeapify(): восстанавливает свойство кучи от определенного узла до конечных узлов.
  • insert(): добавляет заданное значение в массив кучи и переупорядочивает элементы на основе их свойства кучи. На каждой новой вставке куча увеличивается равномерно, а размер увеличивается на единицу.
  • getMax(): возвращает максимальное значение в куче (корневой узел) без изменения кучи. Обратите внимание, что временная сложность здесь — постоянное времяО (1)О ( 1 )
  • removeMax(): возвращает и удаляет максимальное значение в куче (подумайте pop()). Временная сложность этой функции находится вO (журнал (n))O ( l o g ( n ) ).

Если размер кучи больше единицы, он сохраняет максимальное значение в переменной, меняет местами это значение с последним листом и удаляет максимальное значение из кучи.

Если куча имеет только один элемент, она удаляет и возвращает значение этого элемента, последним условием является то, что если куча пуста, она возвращает null.

__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();

Как построить минимальную кучу

Интуитивно мы можем сказать, что элементы в минимальной куче следуют свойству минимальной кучи, поскольку это противоположно максимальным кучам. Ключ родительского узла всегда меньше ключа обоих дочерних узлов. Чтобы построить минимальную кучу, мы:

  • Создайте новый дочерний узел в конце кучи (последний уровень).
  • Добавьте новый ключ к этому узлу (добавьте его в массив).
  • Перемещайте дочерний элемент вверх, пока не дойдете до корневого узла, и свойство кучи не будет удовлетворено.

Чтобы удалить / удалить корневой узел в минимальной куче:

  • Удалите корневой узел.
  • Переместите ключ последнего дочернего элемента в root.
  • Сравните родительский узел с его дочерними узлами.
  • Если значение родительского узла больше дочерних узлов, поменяйте их местами и повторяйте, пока свойство кучи не будет удовлетворено.

Реализация Min Heap в JavaScript

Прежде чем мы перейдем к созданию минимальной кучи, обратите внимание, что ее реализация аналогична реализации Max Heap. minHeapify()восстанавливает свойство кучи. 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())

Задача кучи: преобразование максимальной кучи в минимальную кучу

Давайте сделаем еще один шаг вперед в нашем обучении с помощью практического задания. Наша цель — преобразовать максимальную кучу в минимальную. Следуйте за нашим решением кода, чтобы увидеть, как это делается.

Постановка проблемы: Реализуйте функцию, 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
}

Попробуйте сами, прежде чем проверять решение

Код решения можно запустить ниже. Мы можем рассматривать данное maxHeapкак обычный массив элементов и переупорядочивать его так, чтобы он точно представлял минимальную кучу. convertMax()Функция восстанавливает свойство кучи на всех узлах от самого низкого родительского узла путем вызова minHeapify()функции на каждом.

Временная сложность построения кучи составляет На)О ( п ). Это верно и для этой проблемы.

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))
Оцените статью
bestprogrammer.ru
Добавить комментарий

© 2024 bestprogrammer.ru
Этот сайт использует cookie для хранения данных. Продолжая использовать сайт, Вы даете свое согласие на работу с этими файлами.