3:56

1. Heap이란?

• 힙은 우선순위 큐의 대표적인 자료구조이다.
• 우선순위큐란 원소에 우선순위가 가장 큰 원소부터 접근이 가능한 자료구조이다.
• 힙의 대표적인 종류로는 최대힙, 최소힙이 있으며 최대힙은 키값이 큰 원소가 높은 우선순위를, 최소힙은 키값이 작은 원소가 높은 우선순위를 가진다.
• 최대힙 - 부모 노드의 원소가 자식 노드의 원소보다 크거나 같은 완전 이진트리
• 최소힙 - 부모 노드의 원소가 자식 노드의 원소보다 작거나 같은 완전 이진트리
• 힙에서 삽입 및 삭제의 시간 복잡도는 O(log2n)이다.

2. (최대)Heap 구현하기

구현할 내용은 아래와 같다.

• heapifyUp(int i) - i번째 인덱스의 값을 부모 노드와 비교하여, 부모 노드의 값이 더 작으면 자리를 교환한다.
• heapifyDwon(int i) - i번째 인덱스의 값을 자식 노드 두 개와 비교하여, 둘 중 큰 자식노드보다 i번째 인덱스 값이 더 작으면 자리를 교환한다.
• insert(E x) - 힙의 적절한 자리에 입력받은 값 x를 입력한다.
• delete() - 루트 노드에 있는 값을 삭제한다.
• max() - 루트 노드에 있는 값을 리턴한다.
• isEmpty() - 힙이 비어있으면 true, 그렇지 않으면 false를 리턴한다.
• clear() - 힙의 모든 내용물을 비운다.
• printAll() - 힙의 모든 내용물을 출력한다.

** 원래 힙에서는 맨 앞의 값에만 접근이 가능하나, 테스트 편의상 printAll() 메서드를 만들어 사용하였다.

1) 인터페이스

public interface heapInterface<E> {
	
	public void insert (E x);
	
	public void delete();
	
	public E max();
	
	public boolean isEmpty();
	
	public void clear();
	
	public void printAll();
	
}

2) 클래스

- 필드 영역

    //필드 영역
	private E[] item;
	private int size;

• item[] - 원소를 저장한다.
• size - 배열에 저장된 원소의 개수를 저장한다.

- 생성자 영역

	//생성자 영역
	public heap(int arraySize) {
		item = (E[]) new Comparable [arraySize];
		size=0;
	}

• 배열의 크기를 입력받아 해당 크기의 배열을 생성한다. size변수는 0으로 초기화한다.

- 메서드 영역

<heapifyUp 메서드 구현>

	private void heapifyUp(int i) {
		
		if (i<0 || i>=item.length) {
			throw new IllegalArgumentException();
		} else {
		int parent = (i-1)/2;
		
		if (((Comparable) item[parent]).compareTo(item[i])<0) {
			E tmp = item[i];
			item[i] = item[parent];
			item[parent] = tmp;
			
		heapifyUp(parent);
			}
		}
	}

• parent 변수에 입력받은 인덱스 노드의 부모 인덱스를 저장한다.
• 만약 입력받은 인덱스 노드의 값보다 부모 노드의 값이 작으면 값을 바꾼다.
• 부모 노드와 인덱스 노드의 값이 같거나, 부모 노드 값이 더 클 때까지 부모 노드에 대하여 해당 과정을 반복한다.
• 만약 입력 받은 인덱스가 범위를 벗어났다면 에러를 리턴한다.

<heapifyDown 메서드 구현>

	private void heapifyDown(int i) {
		
		int left = 2*i+1;
		int right = 2*i+2;
		int max = i;
		if (i<0 || i>item.length) {
			throw new IllegalArgumentException();
		} else {
			if (left <=size-1) {
		if (((Comparable) item[max]).compareTo(item[left])<0) {
			max = left;
		} 
		if (((Comparable) item[max]).compareTo(item[right])<0) {
			max = right;
		}
		
		if (max!=i) {
			E tmp = item[i];
			item[i] = item[max];
			item[max] = tmp;
			
			heapifyDown(max); }
			}
		}
	}

• left 변수에 입력받은 인덱스 노드의 왼쪽 자식 노드 인덱스, right 변수에 오른쪽 자식 노드 인덱스를 저장한다.
• max 변수에 입력받은 인덱스를 저장한다.
• left 변수가 범위를 벗어나지 않는 동안 아래 과정을 반복한다.
• max 인덱스의 값과 left, right 인덱스 값을 비교하여 max 인덱스에 가장 큰 값의 인덱스가 들어오게 한다.
• max의 값이 입력받은 값과 다르면(자식 노드중에 더 큰 값이 있다면) 입력 받은 인덱스 노드와 max 인덱스 노드의 자리를 바꾼다.
• 입력받은 인덱스가 범위를 벗어났다면 에러를 리턴한다.

<insert 메서드 구현>

	@Override
	public void insert(E x) {
		if (size==item.length) {
			throw new IllegalArgumentException();
		} else {
		item[size]=x;
		heapifyUp(size);
		size++;
		}
	}

• 힙의 끝에 입력받은 값을 추가한다.
• heapifyUp을 통해 해당 노드가 적절한 자리를 찾게 한다.
• size 변수를 1 증가시킨다. 
• 만약 힙에 빈 자리가 없었다면 에러를 리턴한다.

<delete 메서드 구현>

	@Override
	public void delete() {
		if (isEmpty()) {
			throw new IllegalArgumentException();
		} else {
		item[0]=item[size-1];
		size--;
		heapifyDown(0);
		}
	}

• 힙의 맨 끝자리에 있던 노드를 루트 노드 자리로 옮긴다.
• size 변수를 1 감소시킨다.
• heapifyDown을 통해 루트 노드 자리의 노드가 적절한 자리를 찾게 한다.
• 만약 힙이 비어 있었다면 에러를 리턴한다.

<max 메서드 구현>

	@Override
	public E max() {
		if (isEmpty()) {
			throw new IllegalArgumentException();
		} else {
		return item[0];
			}
		}

• 힙이 비어 있다면 에러를 리턴하고, 그렇지 않다면 루트 노드의 값을 리턴한다.

<isEmpty 메서드 구현>

	@Override
	public boolean isEmpty() {
		return (size==0);
	}

• size 변수가 0인지 여부를 리턴한다.

<clear 메서드 구현>

	@Override
	public void clear() {
		item = (E[]) new Comparable [size];
		size=0;
	}

• item 배열과 size 변수를 초기화한다.

<printAll 메서드 구현>

	@Override
	public void printAll() {
		for (int i=0; i<size; i++) {
			System.out.print(item[i]+" ");
		}

• 인덱스 0부터 배열 끝까지 순회하며 해당 인덱스의 값을 출력한다.

-전체 코드

public class heap<E> implements heapInterface<E> {
	
	//필드 영역
	private E[] item;
	private int size;
	
	//생성자 영역
	public heap(int arraySize) {
		item = (E[]) new Comparable [arraySize];
		size=0;
	}
	
	//메서드 영역
	
	private void heapifyUp(int i) {
		
		if (i<0 || i>=item.length) {
			throw new IllegalArgumentException();
		} else {
		int parent = (i-1)/2;
		
		if (((Comparable) item[parent]).compareTo(item[i])<0) {
			E tmp = item[i];
			item[i] = item[parent];
			item[parent] = tmp;
			
		heapifyUp(parent);
			}
		}
	}
	
	private void heapifyDown(int i) {
		
		int left = 2*i+1;
		int right = 2*i+2;
		int max = i;
		if (i<0 || i>item.length) {
			throw new IllegalArgumentException();
		} else {
			if (left <=size-1) {
		if (((Comparable) item[max]).compareTo(item[left])<0) {
			max = left;
		} 
		if (((Comparable) item[max]).compareTo(item[right])<0) {
			max = right;
		}
		
		if (max!=i) {
			E tmp = item[i];
			item[i] = item[max];
			item[max] = tmp;
			
			heapifyDown(max); }
			}
		}
	}
	
	@Override
	public void insert(E x) {
		if (size==item.length) {
			throw new IllegalArgumentException();
		} else {
		item[size]=x;
		heapifyUp(size);
		size++;
		}
	}

	@Override
	public void delete() {
		if (isEmpty()) {
			throw new IllegalArgumentException();
		} else {
		item[0]=item[size-1];
		size--;
		heapifyDown(0);
		}
	}

	@Override
	public E max() {
		if (isEmpty()) {
			throw new IllegalArgumentException();
		} else {
		return item[0];
			}
		}

	@Override
	public boolean isEmpty() {
		return (size==0);
	}

	@Override
	public void clear() {
		item = (E[]) new Comparable [size];
		size=0;
	}

	@Override
	public void printAll() {
		for (int i=0; i<size; i++) {
			System.out.print(item[i]+" ");
		}
		
	}

}

3) 결과 확인하기

- 코드

public class Test {
	public static void main(String[] args) {
	
		heap<Integer> lst = new heap<>(64);
		
		lst.insert(100);
		
		lst.insert(300);
		
		lst.insert(400);
		
		lst.insert(200);
		
		lst.printAll();
		
		System.out.println();
		
		//100,200,300,400을 차례로 입력하고 출력합니다.
		
		lst.delete();
		
		lst.printAll();
		
		System.out.println();
		
		lst.delete();
		
		lst.printAll();
		
		System.out.println();
		
		//루트에 해당하는 값을 삭제하고 출력합니다.
		
		System.out.println(lst.isEmpty());
		
		System.out.println(lst.max());
		
		//lst가 비었는지 여부와 현재 루트에 있는 값을 출력합니다.
		
		
	}
}

- 결과