DAA - Binary Heap

Existem vários tipos de heap, entretanto, neste capítulo, discutiremos o heap binário. UMAbinary heapé uma estrutura de dados, que se parece com uma árvore binária completa. A estrutura de dados heap obedece às propriedades de ordenação discutidas abaixo. Geralmente, um Heap é representado por uma matriz. Neste capítulo, estamos representando um heap porH.

Como os elementos de um heap são armazenados em uma matriz, considerando o índice inicial como 1, a posição do nó pai de i^th elemento pode ser encontrado em ⌊ i/2 ⌋. Filho esquerdo e filho direito dei^th o nó está na posição 2i e 2i + 1.

Um heap binário pode ser classificado ainda como um max-heap ou um min-heap com base na propriedade do pedido.

Max-Heap

Nesse heap, o valor da chave de um nó é maior ou igual ao valor da chave do filho mais velho.

Conseqüentemente, H[Parent(i)] ≥ H[i]

Min-Heap

No heap médio, o valor-chave de um nó é menor ou igual ao valor-chave do filho mais baixo.

Conseqüentemente, H[Parent(i)] ≤ H[i]

Nesse contexto, as operações básicas são mostradas a seguir em relação ao Max-Heap. A inserção e exclusão de elementos em e de pilhas precisam de rearranjo de elementos. Conseqüentemente,Heapify função precisa ser chamada.

Representação de Matriz

Uma árvore binária completa pode ser representada por um array, armazenando seus elementos usando travessia de ordem de nível.

Vamos considerar um heap (como mostrado abaixo) que será representado por um array H.

Considerando o índice inicial como 0, usando travessia de ordem de nível, os elementos são mantidos em uma matriz da seguinte maneira.

Index	0	1	2	3	4	5	6	7	8	...
elements	70	30	50	12	20	35	25	4	8	...

Nesse contexto, as operações no heap estão sendo representadas em relação ao Max-Heap.

Para encontrar o índice do pai de um elemento no índice i, o seguinte algoritmo Parent (numbers[], i) é usado.

Algorithm: Parent (numbers[], i) 
if i == 1 
   return NULL 
else 
   [i / 2]

O índice do filho esquerdo de um elemento no índice i pode ser encontrado usando o seguinte algoritmo, Left-Child (numbers[], i).

Algorithm: Left-Child (numbers[], i) 
If 2 * i ≤ heapsize 
   return [2 * i] 
else 
   return NULL

O índice do filho certo de um elemento no índice i pode ser encontrado usando o seguinte algoritmo, Right-Child(numbers[], i).

Algorithm: Right-Child (numbers[], i) 
if 2 * i < heapsize 
   return [2 * i + 1] 
else 
   return NULL

↰ Previous page Next page ↱