자바(Java) 예제: 최대 힙 (Max Heap)

자료구조 학습용 예제입니다.

힙과 배열

힙(Heap): 데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 완전 이진 트리(Complete Binary Tree)
완전 이진 트리: 노드를 삽입할 때 최하단 왼쪽 노드부터 차례대로 삽입하는 트리
일반적으로 힙 구현시 배열 자료구조를 활용함
배열은 인덱스가 0번부터 시작하지만, 힙 구현의 편의를 위해, root 노드 인덱스 번호를 1로 지정하면, 구현이 좀더 수월
부모 노드 인덱스 번호 (parent node’s index) = 자식 노드 인덱스 번호 (child node’s index) // 2 (// : 몫만 구함)
왼쪽 자식 노드 인덱스 번호 (left child node’s index) = 부모 노드 인덱스 번호 (parent node’s index) * 2
오른쪽 자식 노드 인덱스 번호 (right child node’s index) = 부모 노드 인덱스 번호 (parent node’s index) * 2 + 1

	package blog.heap;

	public class Card {
	private int number;
	private String description;

	public Card(int number) {
	super();
	this.number = number;
	this.description = "CARD";
	}

	public Card(int number, String description) {
	super();
	this.number = number;
	this.description = description;
	}

	public int getNumber() {
	return number;
	}

	public void setNumber(int number) {
	this.number = number;
	}

	public String getDescription() {
	return description;
	}

	public void setDescription(String description) {
	this.description = description;
	}

	@Override
	public String toString() {
	return "Card [number=" + number + ", description=" + description + "]";
	}


	}

view raw

Card.java

hosted with ❤ by GitHub

	package blog.heap;

	import java.util.ArrayList;
	import java.util.List;

	public class Heap {

	private List<Card> heapArr;

	public Heap(Card card) {
	heapArr = new ArrayList<>();
	heapArr.add(0, null);
	heapArr.add(1, card);
	}

	public List<Card> getList() {
	List<Card> outArr = new ArrayList<>(heapArr);
	outArr.remove(0);
	return outArr;
	}

	private void swap(int idx1, int idx2) {
	Card index1Card = heapArr.get(idx1);
	Card index2Card = heapArr.get(idx2);
	heapArr.set(idx1, index2Card);
	heapArr.set(idx2, index1Card);
	}

	public Card getCardByNumber(int number) {
	for(Card c : heapArr) {
	if(c == null) {
	continue;
	} else if(c.getNumber() == number) {
	return c;
	}
	}
	return null;
	}

	public boolean insert(Card card) {
	if(heapArr.size() == 1) {
	heapArr.add(card);
	return true;
	} else if(getCardByNumber(card.getNumber()) != null) {
	System.out.println(card.getNumber() + ": == 이미 존재하는 값입니다. ==");
	return false;
	}

	heapArr.add(card);

	// rearrange heapArr
	int insertedIndex = heapArr.size() – 1;

	do {

	int parentIndex = insertedIndex / 2;
	// System.out.println(insertedIndex + ":" + parentIndex);

	// NullException 방지
	if (parentIndex == 0) {
	break;
	}
	if (heapArr.get(parentIndex).getNumber() < heapArr.get(insertedIndex).getNumber()) {

	// Swap
	swap(parentIndex, insertedIndex);

	insertedIndex = parentIndex;

	} else {
	break;
	}
	} while(true);
	return true;
	}

	public Card pop() {
	//System.out.println("POP시작");
	if (heapArr.size() <= 1) {
	return null;
	}

	Card card = heapArr.get(1);
	swap(1, heapArr.size() – 1);
	heapArr.remove(heapArr.size() – 1);

	// rearrange heapArr

	int poppedIndex = 1;
	int leftChildIndex, rightChildIndex;

	do {
	// 자식들은 poppedIndex가 갱신될때마다 재지정해야함
	leftChildIndex = poppedIndex * 2;
	rightChildIndex = poppedIndex * 2 + 1;

	// case1: 왼쪽 자식 노드도 없을 때 – 자식 노드가 존재할 수 없음
	// System.out.println("leng " + leftChildIndex + ":" + heapArr.size() );
	if (leftChildIndex >= heapArr.size()) {
	break;
	} else if(rightChildIndex >= heapArr.size()) {
	// case2: 오른쪽 자식 노드만 없을 때 – 왼쪽은 있을 때
	if(heapArr.get(poppedIndex).getNumber() < heapArr.get(leftChildIndex).getNumber() ) {
	swap(poppedIndex, leftChildIndex);
	poppedIndex = leftChildIndex;
	} else {
	break;
	}
	} else {
	// case3: 왼쪽, 오른쪽 자식 노드 모두 있을 때
	if(heapArr.get(leftChildIndex).getNumber() > heapArr.get(rightChildIndex).getNumber()) {
	if(heapArr.get(poppedIndex).getNumber() < heapArr.get(leftChildIndex).getNumber() ) {
	swap(poppedIndex, leftChildIndex);
	poppedIndex = leftChildIndex;
	} else {
	break;
	}
	} else {
	if(heapArr.get(poppedIndex).getNumber() < heapArr.get(rightChildIndex).getNumber() ) {
	swap(poppedIndex, rightChildIndex);
	poppedIndex = rightChildIndex;
	} else {
	break;
	}
	}
	}

	} while(true);


	return card;
	}
	}

view raw

Heap.java

hosted with ❤ by GitHub

	package blog.heap;

	import java.util.Arrays;
	import java.util.Collections;
	import java.util.List;
	import java.util.stream.Collectors;

	public class HeapTest {
	public static void main(String[] args) {
	Heap heap = new Heap(new Card(15));
	heap.insert(new Card(15));

	int[] nums = new int[100];

	// 1~100 일괄 채워넣기
	for (int i = 0; i < nums.length; i++) {
	nums[i] = i + 1;
	}

	List<Integer> list = Arrays.stream( nums ).boxed().collect( Collectors.toList() );
	Collections.shuffle(list); // 섞기
	List<Integer> selection = list.subList(0, 29); // get 30 numbers

	for(int i : selection) {
	//System.out.println(i);
	heap.insert(new Card(i));
	}

	for(int i = 1; i <= 20; i++) {
	System.out.println("popped " + i + ": " + heap.pop());
	}

	for(Card c : heap.getList()) {
	System.out.println(c);
	}

	System.out.println("List size: " + heap.getList().size());

	}
	}