Двоичная куча

01.01.2020Heap

Двоичная куча — это двоичное дерево со следующими свойствами.
1) Это полное дерево (все уровни полностью заполнены, за исключением, возможно, последнего уровня, и на последнем уровне все ключи как можно левее). Это свойство Binary Heap делает их пригодными для хранения в массиве.

2) Двоичная куча — это либо минимальная куча, либо максимальная куча. В минимальной двоичной куче ключ в корневом каталоге должен быть минимальным среди всех ключей, присутствующих в двоичной куче. Одно и то же свойство должно быть рекурсивно истинным для всех узлов в двоичном дереве. ФИЛЬМЫ ПОХОЖИЕ НА MinHeap

Примеры Min Heap:

            10                      10
         /      \               /       \  
       20        100          15         30  
      /                      /  \        /  \
    30                     40    50    100   40

Как представлена двоичная куча?
Двоичная куча — это полное двоичное дерево. Бинарная куча обычно представляется в виде массива.

Корневой элемент будет в Arr [0].
Ниже в таблице приведены индексы других узлов для i- ^го узла, то есть Arr [i]:
Arr[(i-1)/2] Returns the parent node
Arr[(2*i)+1] Returns the left child node
Arr[(2*i)+2] Returns the right child node

Метод обхода, используемый для достижения представления Array, — Level Order

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

Применение кучи:
1) Сортировка кучи : Сортировка кучи использует двоичную кучу для сортировки массива за O (nLogn).

2) Приоритетная очередь. Приоритетные очереди могут быть эффективно реализованы с использованием двоичной кучи, поскольку она поддерживает операции вставки (), удаления () и extractmax (), lowerKey () за время O (logn). Биномоальная куча и куча Фибоначчи — это разновидности бинарной кучи. Эти варианты выполняют объединение также эффективно.

3) Алгоритмы графа: очереди приоритетов особенно используются в алгоритмах графа, таких как кратчайший путь Дейкстры и минимальное остовное дерево Прима .

4) Многие проблемы могут быть эффективно решены с помощью кучи. Смотрите ниже, например.
а) K-й по величине элемент в массиве .
б) Сортировать почти отсортированный массив /
в) объединить отсортированные массивы .

Операции на Min Heap:
1) getMini (): возвращает корневой элемент Min Heap. Сложность времени этой операции O (1).

2) extractMin (): удаляет минимальный элемент из MinHeap. Сложность времени этой операции равна O (Logn), так как эта операция должна поддерживать свойство heap (вызывая heapify ()) после удаления root.

3) lowerKey (): уменьшает значение ключа. Временная сложность этой операции составляет O (Logn). Если значение ключа уменьшается для узла больше, чем для родительского узла, нам ничего не нужно делать. В противном случае нам нужно пройти вверх, чтобы исправить нарушенное свойство кучи.

4) insert (): для вставки нового ключа требуется время O (Logn). Мы добавляем новый ключ в конце дерева. Если новый ключ больше, чем его родитель, тогда нам не нужно ничего делать. В противном случае нам нужно пройти вверх, чтобы исправить нарушенное свойство кучи.

5) delete (): удаление ключа также занимает O (Logn) время. Мы заменяем ключ, который будет удален, минимальным бесконечным, вызывая lowerKey (). После lowerKey (), минус бесконечное значение должно достигнуть корня, поэтому мы вызываем extractMin () для удаления ключа.

Ниже приведена реализация основных операций кучи.

C ++

// Программа на C ++ для демонстрации общих операций двоичной кучи
#include<iostream>
#include<climits>

using namespace std;

// Прототип служебной функции для замены двух целых чисел

void swap(int *x, int *y);

// Класс для Min Heap

class MinHeap

{

int *harr; // указатель на массив элементов в куче

int capacity; // максимально возможный размер кучи min

int heap_size; // Текущее количество элементов в мин куче

public:

// Конструктор

MinHeap(int capacity);

// сложить поддерево с корнем по заданному индексу

void MinHeapify(int );

int parent(int i) { return (i-1)/2; }

// получить индекс левого потомка узла по индексу i

int left(int i) { return (2*i + 1); }

// получить индекс правого потомка узла по индексу i

int right(int i) { return (2*i + 2); }

// извлечь корень, который является минимальным элементом

int extractMin();

// Уменьшаем значение ключа key в index i до new_val

void decreaseKey(int i, int new_val);

// Возвращает минимальный ключ (ключ в корне) из кучи min

int getMin() { return harr[0]; }

// Удаляет ключ, хранящийся в индексе i

void deleteKey(int i);

// Вставляем новый ключ 'k'

void insertKey(int k);

};

// Конструктор: строит кучу из заданного массива a [] заданного размера

MinHeap::MinHeap(int cap)

{

heap_size = 0;

capacity = cap;

harr = new int[cap];

}

// Вставляем новый ключ 'k'

void MinHeap::insertKey(int k)

{

if (heap_size == capacity)

{

cout << "\nOverflow: Could not insertKey\n";

return;

}

// Сначала вставляем новый ключ в конце

heap_size++;

int i = heap_size - 1;

harr[i] = k;

// Исправляем свойство min heap, если оно нарушено

while (i != 0 && harr[parent(i)] > harr[i])

{

swap(&harr[i], &harr[parent(i)]);

i = parent(i);

}

// Уменьшает значение ключа по индексу 'i' до new_val. Предполагается, что
// new_val меньше, чем harr [i].

void MinHeap::decreaseKey(int i, int new_val)

{

harr[i] = new_val;

while (i != 0 && harr[parent(i)] > harr[i])

{

swap(&harr[i], &harr[parent(i)]);

i = parent(i);

}

// Метод удаления минимального элемента (или корня) из минимальной кучи

int MinHeap::extractMin()

{

if (heap_size <= 0)

return INT_MAX;

if (heap_size == 1)

{

heap_size--;

return harr[0];

}

// Сохраняем минимальное значение и удаляем его из кучи

int root = harr[0];

harr[0] = harr[heap_size-1];

heap_size--;

MinHeapify(0);

return root;

}

// Эта функция удаляет ключ по индексу i. Сначала уменьшено значение до минус
// бесконечно, затем вызывает extractMin ()

void MinHeap::deleteKey(int i)

{

decreaseKey(i, INT_MIN);

extractMin();

}

// Рекурсивный метод, чтобы накапливать поддерево с корнем по заданному индексу
// Этот метод предполагает, что поддеревья уже сложены

void MinHeap::MinHeapify(int i)

{

int l = left(i);

int r = right(i);

int smallest = i;

if (l < heap_size && harr[l] < harr[i])

smallest = l;

if (r < heap_size && harr[r] < harr[smallest])

smallest = r;

if (smallest != i)

{

swap(&harr[i], &harr[smallest]);

MinHeapify(smallest);

}

// Утилита для замены двух элементов

void swap(int *x, int *y)

{

int temp = *x;

*x = *y;

*y = temp;

}

// Программа драйвера для проверки вышеуказанных функций

int main()

{

MinHeap h(11);

h.insertKey(3);

h.insertKey(2);

h.deleteKey(1);

h.insertKey(15);

h.insertKey(5);

h.insertKey(4);

h.insertKey(45);

cout << h.extractMin() << " ";

cout << h.getMin() << " ";

h.decreaseKey(2, 1);

cout << h.getMin();

return 0;

}

питон

# Программа Python для демонстрации общих операций двоичной кучи

# Импорт функций кучи из библиотеки Python

from heapq import heappush, heappop, heapify

# heappop - выталкивает и возвращает наименьший элемент из кучи
# heappush - поместить элемент значения в кучу, сохраняя
# куча неизменна
# heapify - преобразовать список в кучу, на месте, в линейное время

# Класс для Min Heap

class MinHeap:

# Конструктор для инициализации кучи

def __init__(self):

self.heap = []

def parent(self, i):

return (i-1)/2

# Вставляет новый ключ 'k'

def insertKey(self, k):

heappush(self.heap, k)

# Уменьшить значение ключа в индексе 'i' до new_val

# Предполагается, что new_val меньше, чем куча [i]

def decreaseKey(self, i, new_val):

self.heap[i] = new_val

while(i != 0 and self.heap[self.parent(i)] > self.heap[i]):

# Поменять кучу [i] на кучу [parent (i)]

self.heap[i] , self.heap[self.parent(i)] = (

self.heap[self.parent(i)], self.heap[i])

# Метод удаления минимального элемента из минимальной кучи

def extractMin(self):

return heappop(self.heap)

# Эта функция удаляет ключ по индексу i. Это сначала уменьшает

# значение до минус бесконечности, а затем вызывает extractMin ()

def deleteKey(self, i):

self.decreaseKey(i, float("-inf"))

self.extractMin()

# Получить минимальный элемент из кучи

def getMin(self):

return self.heap[0]

# Драйвер pgoratm для проверки вышеуказанной функции

heapObj = MinHeap()

heapObj.insertKey(3)

heapObj.insertKey(2)

heapObj.deleteKey(1)

heapObj.insertKey(15)

heapObj.insertKey(5)

heapObj.insertKey(4)

heapObj.insertKey(45)

print heapObj.extractMin(),

print heapObj.getMin(),

heapObj.decreaseKey(2, 1)

print heapObj.getMin()

# Этот код предоставлен Nikhil Kumar Singh (nickzuck_007)

Выход:

2 4 1

Практика кодирования в куче
Все статьи в куче
Тест на кучу
PriorityQueue: реализация двоичной кучи в библиотеке Java

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Двоичная куча

0.00 (0%) 0 votes

Arr[(i-1)/2]	Returns the parent node
Arr[(2*i)+1]	Returns the left child node
Arr[(2*i)+2]	Returns the right child node