[DS] Heap

1. Heap

힙은 Tree 구조를 기반으로 한 자료구조의 일종으로 배열로 구현한 Complete Binary Tree (완전이진트리) 구조로 이루어져 있다.

힙은 root 노드에 위치하는 값의 성질에 따라 max heap과 min heap 두가지로 나뉜다.

 

1) max heap: 각 노드의 값이 해당 child 노드들의 값보다 큰 값을 가지는 완전 이진 트리. 루트노드가 트리에서 가장 큰 값을 가진다.

2) min heap: 각 노드의 값이 해당 child 노드들의 값보다 작은 값을 가지는 완전 이진 트리. 루트노드가 트리에서 가장 작은 값을 가진다.

2. 배열을 통한 구현

heap을 배열로 구현하게 되면 root 노드의 인덱스가 0이 되고, 뒤이어서 나머지 노드들의 값이 저장된다. 이때 heap은 완전 이진 트리 구조이기 때문에 부모 노드의 인덱스와 자식 노드의 인덱스 간에 다음과 같은 관계가 생긴다.

 

i 번째 노드에 대해서

- parent node의 인덱스: (i - 1) / 2

- left child node의 인덱스: (i * 2) + 1

- right child node의 인덱스: (i * 2) + 2

 

max heap 또는 min heap은 루트 노드가 최대 또는 최솟 값을 가지므로 이를 탐색하는 시간은 O(1) 이다. 하지만 heap 의 구조를 계속 유지하기 위해서 heapify 과정을 거쳐야 하는데, 이 과정에서 O(log N)의 시간복잡도를 가지게 된다. heapify는 부모 노드와 자식 노드의 관계를 통해서 구현할 수 있다.

 

insert 또는 delete가 발생하게 되면 heap의 구조를 유지하면서 각 노드들의 위치를 재배열해주어야 한다. 이때 각 노드들은 parent와 child node 들과의 값 비교를 통해서 자리를 찾아가게 된다.

 

max heap의 경우에는 insert가 발생하게 되면 배열의 가장 마지막 자리에 새로운 노드의 값을 넣고 parent와 비교한다. 새로운 노드의 인덱스가 i 일때, parent의 값보다 작아지거나 i가 0이 될때까지 parent node의 인덱스인 (i - 1) / 2의 값과 비교하여 자리를 찾아간다. 반대로 delete 의 경우 해당 자리에 올 자리를 찾아서 child 노드들 (i * 2) + 1과 (i * 2) + 2 를 비교하여 자리를 찾아간다.

3. 자바를 이용한 heap 구현

package DataStructure.Tree;

import java.util.Arrays;
import java.util.Comparator;

public class CustomHeap implements CustomTree {
    private static final int DEFAULT_CAPACITY = 10;

    private Object[] elementData;

    private int size;

    private final Comparator<Integer> comparator;

    public CustomHeap() {
        this(DEFAULT_CAPACITY, null);
    }

    public CustomHeap(int size, Comparator<Integer> comparator) {
        if(size < 1) {
            throw new IllegalArgumentException();
        }
        this.elementData = new Object[size];
        this.comparator = comparator;
        this.size = 0;
    }

    private Object[] grow() {
        return this.elementData = Arrays.copyOf(this.elementData, this.elementData.length * 2);
    }

    private void siftUp(int index, int target) {
        if(this.comparator != null) {
            siftUpUsingComparator(index, target, this.elementData, this.comparator);
        } else {
            siftUpComparable(index, target, this.elementData);
        }
    }

    private static void siftUpUsingComparator(int index, int target, Object[] es, Comparator<Integer> cmp) {
        while(0 < index) {
            int parent = (index - 1) / 2;
            Object e = es[parent];
            if(cmp.compare(target, (Integer) e) > 0)
                break;
            es[index] = e;
            index = parent;
        }
        es[index] = target;
    }

    private static void siftUpComparable(int index, int target, Object[] es) {
        Comparable<Integer> key = (Comparable<Integer>) target;
        while(0 < index) {
            int parent = (index - 1) / 2;
            Object e = es[parent];
            if(key.compareTo((Integer) e) > 0)
                break;
            es[index] = e;
            index = parent;
        }
        es[index] = key;
    }

    @Override
    public boolean insert(int value) {
        // check the value is unique or not
        for(int i = 0; i < this.size; i++) {
            if(this.elementData[i].equals(value)) {
                return false;
            }
        }

        // check array size
        if(this.elementData.length <= size) {
            this.elementData = grow();
        }

        // compare and insert
        siftUp(size, value);
        this.size++;
        return true;
    }

    private void siftDown(int index, int target) {
        if(comparator != null) {
            siftDownUsingComparator(index, target, this.elementData, this.size, this.comparator);
        } else {
            siftDownComparable(index, target, this.elementData, this.size);
        }
    }

    private static void siftDownUsingComparator(int index, int target, Object[] es, int size, Comparator<Integer> cmp) {
        while(index * 2 + 1 <= size) {
            int child = (index << 1) + 1;
            Object c = es[child];
            int right = child + 1;
            if(right < size && cmp.compare((Integer) c, (Integer) es[right]) > 0)
                c = es[child = right];
            if(cmp.compare(target, (Integer) c) <= 0)
                break;
            es[index] = c;
            index = child;
        }
        es[index] = target;
    }

    @SuppressWarnings("unchecked")
    private static void siftDownComparable(int index, int target, Object[] es, int size) {
        Comparable<Integer> key = (Comparable<Integer>) target;
        while(index * 2 + 1 <= size) {
            int child = (index << 1) + 1;
            Object c = es[child];
            int right = child + 1;
            if(right < size && ((Comparable<Integer>) c).compareTo((Integer) es[right]) > 0)
                c = es[child = right];
            if(key.compareTo((Integer) c) <= 0)
                break;
            es[index] = c;
            index = child;
        }
        es[index] = key;
    }

    private void removeAt(int index) {
        int size = --this.size;
        if(size == index) {
            this.elementData[size] = null;
        } else {
            Integer moved = (Integer) this.elementData[size];
            elementData[size] = null;
            siftDown(index, moved);
            if(this.elementData[index] == moved) {
                siftUp(index, moved);
                if(this.elementData[index] != moved)
                    return ;
            }
        }
    }

    @Override
    public boolean remove(int value) {
        for(int i = 0; i <= this.size; i++) {
            if(this.elementData[i].equals(value)) {
                removeAt(i);
                return true;
            }
        }
        return false;
    }

    private void preOrder(int index) {
        System.out.print(elementData[index] + " ");
        int next = index * 2 + 1;
        if(next < this.size) {
            preOrder(next);
        }
        if(next + 1 < this.size) {
            preOrder(next + 1);
        }
    }

    @Override
    public void preOrder() {
        if(this.size != 0)
            preOrder(0);
        System.out.println();
    }

    private void inOrder(int index) {
        int next = index * 2 + 1;
        if(next < this.size) {
            inOrder(next);
        }
        System.out.print(this.elementData[index] + " ");
        if(next + 1 < this.size) {
            inOrder(next + 1);
        }
    }

    @Override
    public void inOrder() {
        if(this.size != 0)
            inOrder(0);
        System.out.println();
    }

    private void postOrder(int index) {
        int next = index * 2 + 1;
        if(next < this.size) {
            postOrder(next);
        }
        if(next + 1 < this.size) {
            postOrder(next + 1);
        }
        System.out.print(this.elementData[index] + " ");
    }

    @Override
    public void postOrder() {
        if(this.size != 0)
            postOrder(0);
        System.out.println();
    }
}

 

[reference]

- https://www.geeksforgeeks.org/heap-data-structure/