6. 비선형자료구조 - 힙(heap)

< 기본 구조 (최소 힙) >

1. 데이터의 연속성이 보장되어 ArrayList로 구현

2. 데이터는 가장 끝에 추가되며 부모 노드와 비교 했을 때 자식 노드가 더 작을 경우 

    부모 자리와 교체 (자식노드가 가장 작은 값이 될 때까지 비교 반복)

3. 최상위 노드 삭제 후 가장 마지막 노드를 최상위로 위치 시키고 해당 값보다 더 작은 자식노드 값이 없을 때 까지 

   자리 교체 반복

 

[1] ArrayList / 객체 생성

class MinHeap{
ArrayList<Integer> heap; //ArrayList생성

public MinHeap() { //객체생성
this.heap = new ArrayList<>();
this.heap.add(0);
}

[2] 데이터 추가 (최소힙)

public void insert(int data) {
heap.add(data); //가장 끝에 추가

int cur = heap.size() - 1;
while (cur > 1 && heap.get(cur / 2) > heap.get(cur)) {
int parentVal = heap.get(cur / 2); //부모의 값
heap.set(cur / 2, data);
heap.set(cur, parentVal);

cur /= 2;

- 가장 끝에 데이터를 추가하고 부모의 값과 비교하며 순회

[3] 데이터 삭제 (최소힙)

// delete 대상 노드는 가장 상위 노드
int target = heap.get(1);

// 마지막 노드를 가장 위로 설정 후 마지막 노드는 삭제
heap.set(1, heap.get(heap.size() - 1));
heap.remove(heap.size() - 1);

- 데이터 삭제는 최상위 노드가 대상, 

if (heap.get(cur) < heap.get(targetIdx)) { // 부모가 작으면 종료
break;
} else { // 부모가 더 크면 자리 바꾸기
int parentVal = heap.get(cur);
heap.set(cur, heap.get(targetIdx));
heap.set(targetIdx, parentVal);
cur = targetIdx;

- 부모 노드가 크면 자식노드와 교체

- 위 조건 반복 순회하며 부모노드가 가장 작을 때 종료 (최소값이 최상위에 오름)

 

---

1. 힙의 기본 구조 이해 가능

   but 스스로 구현 불가 

3. 자바의 정석 조건/반복문 지나왔더니 조건/반복식 이해가 잘 됨

   but 그 외 함수 이해 불가..! (아직 알고 싶지도 않다 ㅠ)

 

(주절주절)

낙심할 필요 없다!! 나는 일단 자바 언어를 떼는 것이 1차 목표!!

공부 시작한지 이제 12일차!!

너무 많은 양을 한번에 넣지 말고 언어의 구조를 이해하며 기록하고 지나가자!!

 

consistency is the key !