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

힙과 배열
  • 힙(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());
}
}

view raw

HeapTest.java

hosted with ❤ by GitHub

문의 | 코멘트 또는 yoonbumtae@gmail.com


카테고리: Java코딩테스트


0개의 댓글

답글 남기기

Avatar placeholder

이메일 주소는 공개되지 않습니다. 필수 필드는 *로 표시됩니다