Max Heap

Max heap : 부모가 자식보다 크다는 규칙에 따라 만든 complete tree.

Min heap : 부모가 자식보다 작다는 규칙에 따라 만든 complete tree.

 

Max heap - Java

public class Heap<E> {
    int lastPosition;
    E[] array;

    public Heap(int maxSize) {
        lastPosition = -1;
        array = (E[]) new Object[maxSize];
    }

    public void swap(int from, int to) {
        E tmp = array[from];
        array[from] = array[to];
        array[to] = tmp;
    }

    public void trickleUp(int child) {
        if (child == 0) {
            return;
        }

        int parent = (child-1)/2; // parent = floor((child-1)/2)

        if (((Comparable<E>)array[parent]).compareTo(array[child]) < 0) {
            swap(parent, child);
            trickleUp(parent);
        }
    }

    public void add(E obj) {
        // 맨 뒤에 추가한 뒤 부모와 계속 비교 (trickleUp)

        array[++lastPosition] = obj;
        trickleUp(lastPosition);
    }

    public void trickleDown(int parent) {
        int left = 2*parent+1; // children = [2*parent+1, 2*parent+2]
        int right = 2*parent+2;

        // 자식이 없는 경우
        if (left > lastPosition)
            return;

        // 왼쪽 자식만 있는 경우
        if (left == lastPosition) {
            if (((Comparable<E>)array[left]).compareTo(array[parent]) > 0)
                swap(left, parent);
            return;
        }

        // 두 자식 모두 있는 경우
        int bigger = right;
        if (((Comparable<E>)array[left]).compareTo(array[right]) > 0)
            bigger = left;

        if (((Comparable<E>)array[bigger]).compareTo(array[parent]) > 0) {
            swap(bigger, parent);
            trickleDown(bigger);
        }
    }

    public E remove() {
        // root 노드는 마지막 노드와 swap을 통해 heap에 포함되지 않은 것으로 간주한다.
        // - root 노드를 삭제하지 않는 이유는 heap sort를 구현하기 위함이다.

        // 새로운 root 노드를 큰 자식과 계속 비교 (trickleDown)

        E tmp = array[0];
        swap(0, lastPosition--);	
        trickleDown(0);
        return tmp;
    }
	
    public List<E> heapSort() {
        // 그냥 원소를 다 지우기만 하면 배열이 정렬된다.

        // 배열 자체가 정렬된 상태긴 하지만 이걸 배열로 반환하려고 하면
        // 런타임에 type erase로 인해 Object[]로 반환된다. 
        // 다루기 까다롭기 때문에 그냥 List<E>로 반환한다. 

        int size = lastPosition+1;
        E[] sorted = (E[]) new Object[size];

        for (int i = 0; i < size; i++) {
            remove();
        }

        for (int i = 0; i < size; i++) {
            sorted[i] = array[i];
        }

        return Arrays.asList(result);
    }
}

 

Max Heap - Python

heap = []

def push(x):
    heap.append(x)
    idx = len(heap)-1
    parent = (idx-1)//2
    while idx > 0 and heap[idx] > heap[parent]:
        heap[idx], heap[parent] = heap[parent], heap[idx]
        idx = parent
        parent = (idx-1)//2

def pop():
    heap[0], heap[-1] = heap[-1], heap[0]
    ret = heap.pop()

    idx = 0
    left, right = 2 * idx + 1, 2 * idx + 2
    while True:
        # 자식 X
        if left >= len(heap):
            return ret
        # 자식 1
        if right >= len(heap):
            if heap[left] > heap[idx]:
                heap[left], heap[idx] = heap[idx], heap[left]
            return ret
        # 자식 2
        maxVal = max(heap[left], heap[right], heap[idx])
        if heap[left] == maxVal > heap[idx]:
            heap[left], heap[idx] = heap[idx], heap[left]
            idx = left
            left, right = 2 * idx + 1, 2 * idx + 2
        elif heap[right] == maxVal > heap[idx]:
            heap[right], heap[idx] = heap[idx], heap[right]
            idx = right
            left, right = 2 * idx + 1, 2 * idx + 2
        else:
            return ret