Heap-egenskapen och arrayrepresentation

# 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')

# 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')

# 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)])

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

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

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).

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]

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)

# 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]

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

# 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')