0Pricing
Coding Interview Prep · Aula

Propriedade de Heap e Representação em Array

Entenda a estrutura de árvore binária completa armazenada como array, derive as fórmulas dos índices de pais e filhos e visualize as operações de subida e descida.

Propriedade de Heap e Representação em Array é uma aula grátis de Coding Interview Prep no CoddyKit. Esta é a aula 1 de 4. Você pode ler a aula completa abaixo gratuitamente — depois pratica ao vivo no navegador com um editor de código integrado e um tutor de IA 24/7. Faz parte do caminho de aprendizado de Coding Interview Prep, e seu progresso é sincronizado entre a web e o app CoddyKit. O curso de Coding Interview Prep inclui 4 aulas no total.

O que é um montículo?

Um montículo é uma árvore binária completa especializada que satisfaz a propriedade do montículo: em um montículo mínimo, cada parent é menor ou igual a seus filhos; em um montículo máximo, cada parent é maior ou igual a seus filhos. Essa propriedade garante que o elemento mínimo (ou máximo) esteja sempre na raiz, permitindo acesso O(1) ao elemento extremo. Os montículos são a estrutura de dados por trás das filas de prioridade.

# Min-heap example:
#         1
#        / \
#       3   2
#      / \ / \
#     7  4 5  6
# Every parent <= its children
# Root (1) is always the minimum

# Max-heap example:
#         9
#        / \
#       7   8
#      / \ / \
#     3  4 5  6
# Every parent >= its children
# Root (9) is always the maximum
print('Heap property: parent dominates all descendants')

Estrutura de árvore binária completa

Um montículo é armazenado como uma árvore binária completa — todos os níveis são totalmente preenchidos, exceto possivelmente o último, que é preenchido da esquerda para a direita. Essa estrutura permite a elegante representação em vetor sem espaço desperdiçado e sem ponteiros. A propriedade de completude garante que a altura do montículo seja sempre floor(log₂ n), garantindo operações push e pop em O(log n).

# Complete binary tree properties:
# 1. All levels filled except possibly the last
# 2. Last level filled from LEFT to right
# 3. For n nodes: height = floor(log2(n))

# NOT complete (last level not left-filled):
#     1
#    / \
#   2   3
#        \
#         4  <- right child without left sibling

# Valid complete binary tree with 4 nodes:
#     1
#    / \
#   2   3
#  /
# 4
print('Complete BT: height = floor(log2(n)) always')

Representação de um montículo em vetor

A estrutura de árvore binária completa permite armazenar um montículo em um vetor simples sem quaisquer ponteiros. Para um nó no índice i (com indexação a partir de zero), seu parent está em (i-1) // 2, seu filho esquerdo em 2i+1 e seu filho direito em 2i+2. Essa aritmética inteira substitui a travessia por ponteiros e torna os montículos extremamente eficientes para o cache.

# Array representation (0-indexed):
# Index:  0  1  2  3  4  5  6
# Array: [1, 3, 2, 7, 4, 5, 6]
# Tree:        1          (index 0)
#             / \         
#            3   2        (indices 1, 2)
#           / \ / \       
#          7  4 5  6      (indices 3,4,5,6)

# Index formulas (0-based):
def parent(i):      return (i - 1) // 2
def left_child(i):  return 2 * i + 1
def right_child(i): return 2 * i + 2

heap = [1, 3, 2, 7, 4, 5, 6]
print('Parent of index 3:', parent(3), '-> value', heap[parent(3)])
print('Left child of 1:', left_child(1), '-> value', heap[left_child(1)])

Restauração para cima: recuperando o montículo após uma inserção

Restauração para cima (também chamada de subida por bolhas ou reorganização para cima) é usada depois da inserção de um novo elemento no final do vetor do montículo. Compare o novo elemento com seu parent; se a propriedade do montículo for violada, troque-os e continue para cima. Repita até que o elemento esteja na posição correta ou alcance a raiz. Isso é executado em O(log n), pois a altura da árvore é O(log n).

def sift_up(heap, i):
    while i > 0:
        p = (i - 1) // 2  # parent index
        if heap[p] > heap[i]:  # min-heap: parent should be smaller
            heap[p], heap[i] = heap[i], heap[p]
            i = p
        else:
            break  # heap property restored

# Demonstrate: insert 0 into an existing min-heap
heap = [1, 3, 2, 7, 4, 5, 6]
heap.append(0)  # add at end
print('Before sift-up:', heap)
sift_up(heap, len(heap) - 1)
print('After sift-up:', heap)  # 0 should bubble to root

Restauração para baixo: recuperando o montículo após uma remoção

Restauração para baixo (reorganização para baixo) é usada depois da remoção da raiz. Mova o último elemento para a raiz e, em seguida, empurre-o para baixo trocando-o repetidamente com o filho menor (no montículo mínimo) até que a propriedade do montículo seja restaurada. Isso também é executado em O(log n). A restauração para cima e a restauração para baixo são os componentes básicos de todas as operações de montículo.

def sift_down(heap, i, n):
    while True:
        smallest = i
        l = 2 * i + 1  # left child
        r = 2 * i + 2  # right child
        if l < n and heap[l] < heap[smallest]:
            smallest = l
        if r < n and heap[r] < heap[smallest]:
            smallest = r
        if smallest == i:
            break  # already in correct position
        heap[i], heap[smallest] = heap[smallest], heap[i]
        i = smallest

heap = [1, 3, 2, 7, 4, 5, 6]
# Pop min: move last to root, then sift-down
heap[0] = heap[-1]
heap.pop()
print('After move last to root:', heap)
sift_down(heap, 0, len(heap))
print('After sift-down:', heap)  # valid min-heap again

Construção de um montículo a partir de um vetor: algoritmo de Floyd

Inserir ingenuamente n elementos um por um custa O(n log n). O algoritmo heapify de Floyd constrói um montículo em O(n) aplicando a restauração para baixo a cada nó não folha, começando pelo último nó não folha (índice n//2 - 1) e trabalhando de trás para frente até a raiz. Os nós folha já são montículos triviais, portanto só precisamos corrigir os nós internos — por isso o trabalho total soma O(n), e não O(n log n).

def build_heap(arr):
    n = len(arr)
    # Start from last non-leaf node: index n//2 - 1
    for i in range(n // 2 - 1, -1, -1):
        sift_down(arr, i, n)
    return arr

arr = [5, 3, 8, 1, 9, 2, 7]
print('Before:', arr)
build_heap(arr)
print('After (min-heap):', arr)  # root should be 1

# Why O(n)? Most nodes are near the bottom (leaves).
# Level k from bottom has ~n/2^k nodes, each needing
# at most k swaps. Sum = n * sum(k/2^k) = O(n).

Ordenação por montículo usando o montículo em vetor

A ordenação por montículo é executada em O(n log n) com O(1) de espaço adicional. Fase 1: construa um montículo máximo a partir do vetor em O(n). Fase 2: extraia repetidamente o máximo trocando a raiz com o último elemento ainda não ordenado e, em seguida, aplique a restauração para baixo ao montículo reduzido. Após n extrações, o vetor estará ordenado em ordem crescente. Esse algoritmo no próprio vetor demonstra como a representação em vetor permite ordenar sem alocar uma estrutura de dados separada.

def sift_down_max(arr, i, n):
    while True:
        largest = i
        l, r = 2*i+1, 2*i+2
        if l < n and arr[l] > arr[largest]: largest = l
        if r < n and arr[r] > arr[largest]: largest = r
        if largest == i: break
        arr[i], arr[largest] = arr[largest], arr[i]
        i = largest

def heap_sort(arr):
    n = len(arr)
    # Build max-heap
    for i in range(n // 2 - 1, -1, -1):
        sift_down_max(arr, i, n)
    # Extract elements one by one
    for end in range(n - 1, 0, -1):
        arr[0], arr[end] = arr[end], arr[0]  # move max to end
        sift_down_max(arr, 0, end)

arr = [5, 3, 8, 1, 9, 2, 7]
heap_sort(arr)
print(arr)  # [1, 2, 3, 5, 7, 8, 9]

Montículo mínimo versus montículo máximo

Um montículo mínimo tem o menor elemento na raiz; fazer pop sempre fornece o mínimo. Um montículo máximo tem o maior elemento na raiz; fazer pop sempre fornece o máximo. Ambos têm estrutura e operações idênticas — apenas a direção da comparação muda. O módulo heapq do Python implementa apenas um montículo mínimo, portanto é necessário negar os valores para simular um montículo máximo.

import heapq

# Python heapq is a MIN-HEAP
min_heap = []
heapq.heappush(min_heap, 5)
heapq.heappush(min_heap, 1)
heapq.heappush(min_heap, 3)
print('Min-heap min:', heapq.heappop(min_heap))  # 1

# Simulate MAX-HEAP by negating values
max_heap = []
for val in [5, 1, 3]:
    heapq.heappush(max_heap, -val)  # negate on push
print('Max-heap max:', -heapq.heappop(max_heap))  # 5 (negate on pop)

# For tuples: heapq sorts by first element
print(min_heap, max_heap)

Resumo da complexidade das operações de montículo

Todas as operações de montículo derivam da restauração para cima e da restauração para baixo, ambas em O(log n). Push: append + restauração para cima = O(log n). Pop: trocar a raiz com o último elemento + restauração para baixo = O(log n). Peek: acessar o índice 0 = O(1). Construção do montículo: O(n) por meio do algoritmo de Floyd. Ordenação por montículo: O(n log n). Essas complexidades tornam os montículos a estrutura ideal quando você precisa repetidamente do mínimo ou do máximo de uma coleção dinâmica.

# Heap complexity summary:
# Operation     | Time       | Space
# --------------|------------|-------
# Push          | O(log n)   | O(1)
# Pop (min/max) | O(log n)   | O(1)
# Peek          | O(1)       | O(1)
# Build from n  | O(n)       | O(1) in-place
# Heap sort     | O(n log n) | O(1)
# nlargest(k,n) | O(n log k) | O(k)

import heapq
data = [5, 3, 8, 1, 9, 2, 7]
print('Top 3 largest:', heapq.nlargest(3, data))  # [9, 8, 7]
print('Top 3 smallest:', heapq.nsmallest(3, data))  # [1, 2, 3]

Padrões práticos de montículos em entrevistas

Os montículos resolvem uma família de problemas de entrevista com um padrão comum: mantenha uma fila de prioridade de k candidatos enquanto percorre n elementos em fluxo. Elementos mais frequentes entre os k primeiros, k pontos mais próximos da origem e agendadores de tarefas usam esse padrão. Reconheça-o quando encontrar: "dado um fluxo de n itens, mantenha os k melhores" — isso sempre exige um montículo de tamanho k, resultando em O(n log k) total time.

import heapq

# Top-K closest points to origin using a max-heap of size k
def k_closest(points, k):
    # Use max-heap (negate distance) of size k
    heap = []
    for x, y in points:
        dist = -(x*x + y*y)  # negate for max-heap
        heapq.heappush(heap, (dist, x, y))
        if len(heap) > k:
            heapq.heappop(heap)  # remove farthest
    return [[x, y] for _, x, y in heap]

points = [[1,3], [-2,2], [5,8], [0,1]]
print(k_closest(points, 2))  # 2 closest to origin

Trocas entre montículo e vetor ordenado

Escolha um montículo quando você precisar apenas de acesso repetido ao mínimo ou ao máximo e a coleção mudar dinamicamente. Escolha um vetor ordenado quando precisar de acesso aleatório por índice ou de consultas de intervalo. A desvantagem do montículo é que ele exige uma busca O(n) por elementos arbitrários; sua vantagem é a inserção/remoção em O(log n) e o acesso O(1) ao mínimo/máximo. Um vetor ordenado tem inserção O(n), mas busca O(log n) por meio de busca binária.

# Trade-off comparison:
# Structure     | insert  | delete_min | search | range_query
# --------------|---------|------------|--------|------------
# Min-heap      | O(logn) | O(logn)    | O(n)   | O(n)
# Sorted array  | O(n)    | O(n)       | O(logn)| O(logn+k)
# BST (balanced)| O(logn) | O(logn)    | O(logn)| O(logn+k)
# Hash map      | O(1)    | O(1)       | O(1)   | O(n)

# Interview heuristic:
# 'Find minimum repeatedly from dynamic collection' -> HEAP
# 'Binary search or range query' -> sorted array or BST
# 'Fast lookup by key' -> hash map
print('Heap = dynamic collection with priority access')

Verificação rápida

Teste sua compreensão dos conceitos de Estruturas de Dados & Algoritmos — Preparação para Entrevistas de Programação desta lição.

Recapitulação da lição

Nesta lição, você aprendeu: a propriedade do montículo e a estrutura de árvore binária completa, a representação em vetor com fórmulas de índice de parent/filho e a restauração para cima e restauração para baixo como componentes básicos de todas as operações de montículo, incluindo a construção O(n) de Floyd. Em seguida, implementaremos heapify e exploraremos o módulo heapq do Python.

Perguntas Frequentes

A aula “Propriedade de Heap e Representação em Array” é grátis?

Sim — o texto completo de “Propriedade de Heap e Representação em Array” é grátis para ler aqui na web. Para praticá-la interativamente (um editor de código integrado e um tutor de IA 24/7) e desbloquear o restante do curso de Coding Interview Prep, atualize para CoddyKit PRO. O curso de Coding Interview Prep inclui 4 aulas no total.

O que vou aprender em “Propriedade de Heap e Representação em Array”?

Entenda a estrutura de árvore binária completa armazenada como array, derive as fórmulas dos índices de pais e filhos e visualize as operações de subida e descida. Você pratica Coding Interview Prep com código prático que executa diretamente no navegador, e um tutor de IA 24/7 responde suas dúvidas enquanto trabalha na aula.

Preciso ter experiência prévia para começar Coding Interview Prep?

Nenhuma experiência prévia é necessária. Coding Interview Prep no CoddyKit é estruturado para alunos iniciantes até avançados, então você pode começar aqui ou desde o início e aprender no seu ritmo. Esta é a aula 1 de 4.

Quanto tempo leva a aula “Propriedade de Heap e Representação em Array”?

A maioria das aulas CoddyKit leva cerca de 5–10 minutos. Cada uma é compacta e interativa, então você faz progresso constante e retoma exatamente de onde parou entre web e app.

Posso escrever e executar código nesta aula de Coding Interview Prep?

Sim. Cada aula de Coding Interview Prep inclui um editor de código integrado, então você escreve e executa código real direto no navegador e recebe feedback de IA instantaneamente — nenhuma configuração local necessária.

Todas as aulas deste curso

  1. Propriedade de Heap e Representação em Array
  2. Heapify, Push e Pop do Zero
  3. heapq do Python e Técnicas de Max-Heap
  4. Mediana de um Fluxo de Dados e Intercalação em K Vias
← Voltar para Coding Interview Prep