Heap(Max) 자료구조 예제

Card.java

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 + "]";
	}
	
	
}

Heap.java

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;
	}
}

HeapTest.java

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());

	}
}