📚 Heap

힙이란 각 노드의 값이 child의 그것보다 작다는 원칙을 지키는 Complete binary tree이다. 그런 만큼 왼쪽부터 값이 이쁘게 들어가게 된다.
보통 Array로 구현하므로 본인도 Array 구현을 진행해보겠다.
이 때는 array의 0번째 칸은 쓰지 않고 1~n까지를 쓰는데, 이는 child과 parent를 계산하기 편하기 때문.

저번 Binary Tree 게시물에도 있지만, i번째 인덱스의 왼쪽 child = i2, 오른쪽 i2 + 1이다.

Priority Queue

우선순위 큐도 힙을 이용해서 구현되는데, 이 때 우선순위 큐는 Query max와 delete max, insert 기능을 가진다.
가장 큰 key를 가진 요소가 root node에 위치한 형상.

⚙️ Functions

• insert : 적절한 위치에 삽입. 이를 구현하기 위해서는 리스트의 가장 끝에 요소를 집어넣는데, 이 때 힙의 성질이 위반될 수 있으므로 Heapify라는 작업을 통해 적절한 위치에 swap을 해준다.

• delete : root node에 있는 값을 삭제한다. 이를 위해 마지막 인덱스의 값을 root로 복사하고, 적절한 위치로 돌아가도록 Heapify를 해준다.

• Heapify : 현재 노드 기준으로 왼쪽과 오른쪽 subtree가 heap일 때, 주어진 노드 기준 heap의 성질이 위반되지 않게 한다.

💻 Implementation

class Heap {
	private int size;
	private int idx;
	private int[] arr;

	public Heap(int n) {
		size = n;
		idx = 0;
		arr = new int[size+1];
	}

	public void insert(int x) {
		if (isFull()) return ;
		arr[++idx] = x;

		int i=idx;
		while (i > 1) {
			if (arr[i] > arr[i/2]) {
				swap(i, i/2);
				i /= 2;
			}
			else break;
		}

	}

	public int deleteMax() {
		int tmp;

		tmp = arr[1];
		arr[1] = arr[idx];
		arr[idx--] = tmp;
		heapify(1);
		return tmp;
	}

	public void heapify(int cur) {
		int maxIdx;

		if (cur*2>idx && cur*2+1>idx)
			return ;

		if (cur*2 <= idx && cur*2+1 <= idx) {
			if (arr[cur*2] > arr[cur*2+1])
				maxIdx = cur*2;
			else
				maxIdx = cur*2+1;
		}
		else
			maxIdx = cur*2;
			
		if (arr[cur] < arr[maxIdx]) {
			swap(cur, maxIdx);
			cur = maxIdx;
			heapify(cur);
		}
	}

	public void swap(int i, int j) {
		int tmp;

		tmp = arr[i];
		arr[i] = arr[j];
		arr[j] = tmp;
	}
	public boolean isFull() {
		return (idx == size);
	}

	public void printAll() {
		for (int i=1;i<=size;i++)
			System.out.print(arr[i] + " ");
		System.out.println();
	}
}

heapify는 재귀로 구현했다. 반복문으로도 충분히 가능하지만, 오히려 재귀를 이용하는게 직관적인 케이스인 것 같고, 시간복잡도의 asymptotic notation에서도 차이는 없다.

⌛️ Time Complexity

• insertion : 삽입은 O(logN)이 걸린다. 힙을 재정렬하는 과정에서 최대 레벨까지 내려갈 수 있는데, complete tree의 최대 레벨은 logn이기 때문.
• 마찬가지로 deletion도 O(logN)이 걸린다.
• 위는 모두 Heapify가 O(logn)의 복잡도를 가지기 때문이다. 사실 배열에 값을 지정하는 것 자체는 상수 복잡도이다.

다음에는 이를 이용한 Heap Sort를 알아보자 !!