Heap(by Array) 구현 코드

Heap class

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

public class Heap<E> {
	private final Comparator<? super E> comparator;
	private static final int DEFAULT_CAPACITY = 10;
	
	private int size;
	
	private Object[] array;
	
	public Heap() {
		this(null);
	}
	
	public Heap(Comparator<? super E> comparator) {
		this.array = new Object[DEFAULT_CAPACITY];
		this.size = 0;
		this.comparator = comparator;
	}
	
	public Heap(int capacity) {
		this(capacity, null);
	}
	
	public Heap(int capacity, Comparator<? super E> comparator) {
		this.array = new Object[capacity];
		this.size = 0;
		this.comparator = comparator;
	}
	
	private int getParent(int index) {
		return index/2;
	}
	
	private int getLeftChild(int index) {
		return index*2;
	}
	
	private int getRightChild(int index) {
		return index*2 + 1;
	}
	
	private void resize(int newCapacity) {
		Object[] newArray = new Object[newCapacity];
		
		for(int i=0; i<=size; i++) {
			newArray[i] = array[i];
		}
		
		this.array = null;
		array = newArray;
	}
	
	// add method
	public void add(E data) {
		if(size + 1 == array.length) {
			resize(array.length*2);
		}
		
		siftUp(size + 1, data);
		size++;
	}
	
	private void siftUp(int index, E target) {
		if(comparator != null) {
			siftUpComparator(index, target, comparator);
		}
		else {
			siftUpComparable(index, target);
		}
	}
	
	private void siftUpComparator(int index, E target, Comparator<? super E> comp) {
		
		while(index>1) {
			int parent = getParent(index);
			Object parentVal = array[parent];
			
			if(comp.compare(target, (E) parentVal) >= 0) {
				break;
			}
			array[index] = parentVal;
			index = parent;
		}
		array[index] = target;
		
	}
	
	private void siftUpComparable(int index, E target) {
		Comparable<? super E> comp = (Comparable<? super E>) target;
		
		while(index>1) {
			int parent = getParent(index);
			Object parentVal = array[parent];
			
			if(comp.compareTo((E)parentVal) >= 0) { // maxHeap을 구현하고 싶다면 연산자를 <= 로 바꾸면 됨
				break;
			}
			
			array[index] = parentVal;
			index = parent;
		}
		array[index] = comp;
	}
	
	//remove method
	@SuppressWarnings("unchecked")
	public E remove() {
		if(array[1] == null) {	
			throw new NoSuchElementException();
		}
	    
		E result = (E) array[1];	
		E target = (E) array[size];
		array[size] = null;	
			
		
		siftDown(1, target);	
			
		return result;
	}
		
		
	
	private void siftDown(int idx, E target) {
		// comparator가 존재할 경우 comparator 을 인자로 넘겨준다.
		if(comparator != null) {
			siftDownComparator(idx, target, comparator);
		}
		else {
			siftDownComparable(idx, target);
		}
	}
		
	// Comparator을 이용한 sift-down
	@SuppressWarnings("unchecked")
	private void siftDownComparator(int idx, E target, Comparator<? super E> comp) {
			
		array[idx] = null;	
		size--;	
				
		int parent = idx;	
		int child;	
			
		
		while((child = getLeftChild(parent)) <= size) {
				
			int right = getRightChild(parent);	
				
			Object childVal = array[child];	 
				
			
			if(right <= size && comp.compare((E) childVal, (E) array[right]) > 0) {
				child = right;
				childVal = array[child];
			}
				
			if(comp.compare(target ,(E) childVal) <= 0){
				break;
			}
			
			array[parent] = childVal;
			parent = child;
		}
			
		array[parent] = target;
			
		if(array.length > DEFAULT_CAPACITY && size < array.length / 4) {
			resize(Math.max(DEFAULT_CAPACITY, array.length / 2));
		}
	 
	}
		
	// Comparable을 이용한 sift-down
	@SuppressWarnings("unchecked")
	private void siftDownComparable(int idx, E target) {
			
		Comparable<? super E> comp = (Comparable<? super E>) target;
			
		array[idx] = null;
		size--;
			
		int parent = idx;
		int child;
	 
		while((child = getLeftChild(parent)) <= size) {
				
			int right = getRightChild(parent);
				
			Object childVal = array[child];
			
			if(right <= size && ((Comparable<? super E>)childVal).compareTo((E)array[right]) > 0) {
				child = right;
				childVal = array[child];
			}
				
			if(comp.compareTo((E) childVal) <= 0){
				break;
			}
			array[parent] = childVal;
			parent = child;
				
		}
		array[parent] = comp;
			
		if(array.length > DEFAULT_CAPACITY && size < array.length / 4) {
			resize(Math.max(DEFAULT_CAPACITY, array.length / 2));
		}
			
	}
	
	public int size() {
		return this.size;
	}
	
	@SuppressWarnings("unchecked")
	public E peek() {
		if(array[1] == null) {
			throw new NoSuchElementException();
		}
		return (E) array[1];
	}
	
	public Object[] toArray() {
		return Arrays.copyOf(array, size+1);
	}
	
}

https://st-lab.tistory.com/161?category=856997
내가 직접 코딩해보고 사이트를 확인하여 수정하는 방법으로 구현을 진행했음