Estrutura de dados heap

Neste tutorial, você aprenderá o que é estrutura de dados heap. Além disso, você encontrará exemplos funcionais de operações de heap em C, C ++, Java e Python.

A estrutura de dados heap é uma árvore binária completa que satisfaz a propriedade heap . Também é chamado de heap binário .

Uma árvore binária completa é uma árvore binária especial na qual

  • cada nível, exceto possivelmente o último, é preenchido
  • todos os nós estão o mais à esquerda possível

Heap Property é a propriedade de um nó no qual

  • (para o heap máximo) a chave de cada nó é sempre maior que seu (s) nó (s) filho (s) e a chave do nó raiz é a maior entre todos os outros nós;
  • (para min heap) a chave de cada nó é sempre menor que o (s) nó (s) filho (s) e a chave do nó raiz é a menor entre todos os outros nós.

Operações de heap

Algumas das operações importantes realizadas em um heap são descritas a seguir, juntamente com seus algoritmos.

Heapify

Heapify é o processo de criação de uma estrutura de dados heap a partir de uma árvore binária. Ele é usado para criar um Min-Heap ou um Max-Heap.

  1. Deixe a matriz de entrada ser
  2. Crie uma árvore binária completa a partir do array
  3. Comece a partir do primeiro índice de nó não folha cujo índice é dado por n/2 - 1.
  4. Defina o elemento atual icomo largest.
  5. O índice da criança esquerda é dado por 2i + 1e o da criança direita é dado por 2i + 2.
    Se leftChildfor maior que currentElement(ou seja, elemento no ithíndice), defina leftChildIndexcomo o maior.
    Se rightChildfor maior do que o elemento em largest, defina rightChildIndexcomo largest.
  6. Trocar largestcomcurrentElement
  7. Repita as etapas 3 a 7 até que as subárvores também estejam empilhadas.

Algoritmo

 Heapify(array, size, i) set i as largest leftChild = 2i + 1 rightChild = 2i + 2 if leftChild > array(largest) set leftChildIndex as largest if rightChild > array(largest) set rightChildIndex as largest swap array(i) and array(largest)

Para criar um Max-Heap:

 MaxHeap(array, size) loop from the first index of non-leaf node down to zero call heapify

Para Min-Heap, leftChilde rightChilddeve ser menor que o pai para todos os nós.

Inserir elemento na pilha

Algoritmo para inserção em Max Heap

 If there is no node, create a newNode. else (a node is already present) insert the newNode at the end (last node from left to right.) heapify the array
  1. Insira o novo elemento no final da árvore.
  2. Heapify a árvore.

Para Min Heap, o algoritmo acima é modificado para que parentNodeseja sempre menor que newNode.

Excluir elemento da pilha

Algoritmo para exclusão em Max Heap

 If nodeToBeDeleted is the leafNode remove the node Else swap nodeToBeDeleted with the lastLeafNode remove noteToBeDeleted heapify the array
  1. Selecione o elemento a ser excluído.
  2. Troque-o pelo último elemento.
  3. Remova o último elemento.
  4. Heapify a árvore.

Para Min Heap, o algoritmo acima é modificado para que ambos childNodessejam maiores e menores que currentNode.

Peek (encontrar max / min)

A operação Peek retorna o elemento máximo de Max Heap ou o elemento mínimo de Min Heap sem excluir o nó.

Para heap máximo e heap mínimo

 return rootNode

Extrair-Max / Min

Extract-Max retorna o nó com valor máximo após removê-lo de um Heap Máx, enquanto Extract-Min retorna o nó com valor mínimo após removê-lo de Min Heap.

Exemplos de Python, Java, C / C ++

Python Java C C ++ 
 # Max-Heap data structure in Python def heapify(arr, n, i): largest = i l = 2 * i + 1 r = 2 * i + 2 if l < n and arr(i) < arr(l): largest = l if r < n and arr(largest) < arr(r): largest = r if largest != i: arr(i),arr(largest) = arr(largest),arr(i) heapify(arr, n, largest) def insert(array, newNum): size = len(array) if size == 0: array.append(newNum) else: array.append(newNum); for i in range((size//2)-1, -1, -1): heapify(array, size, i) def deleteNode(array, num): size = len(array) i = 0 for i in range(0, size): if num == array(i): break array(i), array(size-1) = array(size-1), array(i) array.remove(num) for i in range((len(array)//2)-1, -1, -1): heapify(array, len(array), i) arr = () insert(arr, 3) insert(arr, 4) insert(arr, 9) insert(arr, 5) insert(arr, 2) print ("Max-Heap array: " + str(arr)) deleteNode(arr, 4) print("After deleting an element: " + str(arr)) 
  // Max-Heap data structure in Java import java.util.ArrayList; class Heap ( void heapify(ArrayList hT, int i) ( int size = hT.size(); int largest = i; int l = 2 * i + 1; int r = 2 * i + 2; if (l hT.get(largest)) largest = l; if (r hT.get(largest)) largest = r; if (largest != i) ( int temp = hT.get(largest); hT.set(largest, hT.get(i)); hT.set(i, temp); heapify(hT, largest); ) ) void insert(ArrayList hT, int newNum) ( int size = hT.size(); if (size == 0) ( hT.add(newNum); ) else ( hT.add(newNum); for (int i = size / 2 - 1; i>= 0; i--) ( heapify(hT, i); ) ) ) void deleteNode(ArrayList hT, int num) ( int size = hT.size(); int i; for (i = 0; i = 0; j--) ( heapify(hT, j); ) ) void printArray(ArrayList array, int size) ( for (Integer i : array) ( System.out.print(i + " "); ) System.out.println(); ) public static void main(String args()) ( ArrayList array = new ArrayList(); int size = array.size(); Heap h = new Heap(); h.insert(array, 3); h.insert(array, 4); h.insert(array, 9); h.insert(array, 5); h.insert(array, 2); System.out.println("Max-Heap array: "); h.printArray(array, size); h.deleteNode(array, 4); System.out.println("After deleting an element: "); h.printArray(array, size); ) )
 // Max-Heap data structure in C #include int size = 0; void swap(int *a, int *b) ( int temp = *b; *b = *a; *a = temp; ) void heapify(int array(), int size, int i) ( if (size == 1) ( printf("Single element in the heap"); ) else ( int largest = i; int l = 2 * i + 1; int r = 2 * i + 2; if (l array(largest)) largest = l; if (r array(largest)) largest = r; if (largest != i) ( swap(&array(i), &array(largest)); heapify(array, size, largest); ) ) ) void insert(int array(), int newNum) ( if (size == 0) ( array(0) = newNum; size += 1; ) else ( array(size) = newNum; size += 1; for (int i = size / 2 - 1; i>= 0; i--) ( heapify(array, size, i); ) ) ) void deleteRoot(int array(), int num) ( int i; for (i = 0; i  = 0; i--) ( heapify(array, size, i); ) ) void printArray(int array(), int size) ( for (int i = 0; i < size; ++i) printf("%d ", array(i)); printf(""); ) int main() ( int array(10); insert(array, 3); insert(array, 4); insert(array, 9); insert(array, 5); insert(array, 2); printf("Max-Heap array: "); printArray(array, size); deleteRoot(array, 4); printf("After deleting an element: "); printArray(array, size); ) 
 // Max-Heap data structure in C++ #include #include using namespace std; void swap(int *a, int *b) ( int temp = *b; *b = *a; *a = temp; ) void heapify(vector &hT, int i) ( int size = hT.size(); int largest = i; int l = 2 * i + 1; int r = 2 * i + 2; if (l hT(largest)) largest = l; if (r hT(largest)) largest = r; if (largest != i) ( swap(&hT(i), &hT(largest)); heapify(hT, largest); ) ) void insert(vector &hT, int newNum) ( int size = hT.size(); if (size == 0) ( hT.push_back(newNum); ) else ( hT.push_back(newNum); for (int i = size / 2 - 1; i>= 0; i--) ( heapify(hT, i); ) ) ) void deleteNode(vector &hT, int num) ( int size = hT.size(); int i; for (i = 0; i  = 0; i--) ( heapify(hT, i); ) ) void printArray(vector &hT) ( for (int i = 0; i < hT.size(); ++i) cout << hT(i) << " "; cout << ""; ) int main() ( vector heapTree; insert(heapTree, 3); insert(heapTree, 4); insert(heapTree, 9); insert(heapTree, 5); insert(heapTree, 2); cout << "Max-Heap array: "; printArray(heapTree); deleteNode(heapTree, 4); cout << "After deleting an element: "; printArray(heapTree); )

Aplicativos de estrutura de dados heap

  • Heap é usado ao implementar uma fila de prioridade.
  • Algoritmo de Dijkstra
  • Classificação de pilha

Artigos interessantes...