2020-02-01

Heap

• heap 의 사전적 의미는 더미 라는 뜻이다. 대충 쌓아 올린다는 뜻이다.
• push : 마지막 요소 (오른쪽 아래) 에 값을 넣고 parent 와 비교하여 바꿔치기 하며 올라온다.
• pop : 맨 위를 빼내고, 마지막 요소 (오른쪽 아래) 를 맨 위로 올린다. 비교하며 내려간다.

구현

• heap push 와 pop 을 간단하게 구현했다. 인터넷에 거창한 구현들이 많다. 다들 너무 거창하고 주석도 너무 자세하다.
• min heap 의 간단한 구현체다. 이 구현은 0번 인덱스 까지 사용한다. 그래서 parent 를 계산하는 식이 조금 다를 수 있다.

import random

def heapPush(arr, val):
    i = len(arr)
    arr.append(val)
    pi = ((i + 1) // 2) - 1
    while i > 0 and arr[i] < arr[pi]:
        arr[i], arr[pi] = arr[pi], arr[i]
        i = pi
        pi = ((i + 1) // 2) - 1

def heapPop(arr):
    minVal = arr[0]
    arr[0] = arr[-1]
    arr.pop()
    i = 0
    while (i * 2) + 1 < len(arr):
        left = (i * 2) + 1
        right = (i * 2) + 2
        if right < len(arr) and arr[left] > arr[right]:
            child = right
        else:
            child = left
        if arr[i] > arr[child]:
            arr[i], arr[child] = arr[child], arr[i]
            i = child
        else:
            break
    return minVal

for _ in range(1000):
    arr = [random.randint(0, 2000) for _ in range(1000)]
    heapArr = []
    for val in arr:
        heapPush(heapArr, val)
    sortedArr = []
    while heapArr:
        sortedArr.append(heapPop(heapArr))
    assert sorted(arr) == sortedArr

private static class Heap<T> {
    private T[] arr;
    private Comparator<T> comparator;
    int pos;

    Heap(T[] arr, Comparator<T> comparator) {
        this.arr = arr;
        this.pos = 0;
        this.comparator = comparator;
    }

    void put(T t) {
        pos++;
        arr[pos] = t;
        int i = pos;
        int parent = i / 2;
        while (parent >= 1 && this.comparator.compare(arr[parent], arr[i]) > 0) {
            T tmp = arr[parent];
            arr[parent] = arr[i];
            arr[i] = tmp;
            i = parent;
            parent = parent / 2;
        }
    }

    T pop() {
        T ret = arr[1];
        arr[1] = arr[pos];
        arr[pos] = null;
        pos -= 1;
        int i = 1;
        while (i * 2 + 1 <= pos) {
            int j;
            int left = i * 2;
            int right = i * 2 + 1;
            if (this.comparator.compare(arr[left], arr[right]) > 0) {
                j = right;
            } else {
                j = left;
            }
            if (this.comparator.compare(arr[i], arr[j]) > 0) {
                T tmp = arr[i];
                arr[i] = arr[j];
                arr[j] = tmp;
                i = j;
            } else {
                break;
            }
        }
        return ret;
    }
}

python heapq

python heapq 를 이용하는 코드다. heapq 의 사용법을 익혀본다.

1. 배열의 절반은 heapify 로 heap 으로 만든다.
2. 나머지 절반은 heappush 로 heap 에 마저 넣는다.
3. 차례대로 빼낸다.
4. 따로 정렬한 배열과 비교한다

import heapq
for _ in range(100):
    arr = [random.randint(0, 2000) for _ in range(1000)]
    # Heapify
    heap = arr[:len(arr)]
    heapq.heapify(heap)
    # heapush
    for v in arr[len(arr):]:
        heapq.heappush(heap, v)
    # heappop
    sortedArr = []
    while heap:
        sortedArr.append(heapq.heappop(heap))
    assert sorted(arr) == sortedArr