데이터 구조 11 (Heap)

Heap

 : Bibary Tree의 일종

 

 - 조건)

1) Coplete binary tree : 꽉 채워진 트리를 뜻함

2 ) Max-Tree :Parent 의 key값 > childern 의 key값

 

 

 

- Heap의 특징

1. 저장된 원소 중에서 가장 큰 원소를 제공 함   Big-O 로는  insert나 delete 모두 O(log n)

ex)큐 = 가장 먼저온 원소 제공   //  스택 = 가장 최에 온 원소 제공

 

2. 일반적으로 [ array ]로 표현 한다.

   

    root=1일 때

  - k번째 원소의 left child : 2*k번째 / right " : 2*k +1 번째

  - k의 parent: k/2

 

 

ADT

: key값을 갖는 원소 저장소

-연산 

: 추가 / 가져오기(삭제) / size / Full check (size(개수) >= Hsize(힙 크기))/ Empty check (size==0)

 

 

---

 

Insert  element t

 

1. 그냥 추가된다고 생각하고 "일단은" 가장 끝(가장 밑 + 가장 오른쪽)으로 들어간다.(complete binary tree니까)

       -> int k;        //새 원소를 넣을 위치 찾는 거 (주소라고 생각하면 편함)

          size++;     //노드 개수 1개 추가

 

2. 끝 위치 의 원소에서 시작하여 다음 작업 반복 

       -> k = csize;   //끝 원소 위치

•      [조건 : parent랑 자신이랑 비교하면서, 자신보다 낮은 값이면]

            [명령: 자리를 바꾼다] (반복)

 

• [조건 : parent 원소값이 더 크거나, root에 도달하면 ]

        [ 현 위치를 원소넣을 곳으로 정한다 ] 

 

        -> while ((k!=1) && (t.score > h[k/2].score)) //끝 원소의 위치가 루트가 아니고, 부모 원소값보다 크면

             h[k] = h[k/2] ;       // 부모노드와 값을 현재 위치로 끌어내린다. [ 값을 바꾼다 ] 

              k / = 2;                //부모노드의 자리로 간다.                             [ 갈 주소를 바꾼다 ] 

         (반복문 탈출) => 부모노드보다 값이 작다 or 루트(k==1)다

 

3. 거기에 원소 값을 넣는다.

              h[k] = t; 

---

 

Delete
가장 큰 값 (=루트)가져온다

 

element t;      //리턴용

element tmp; //자리 찾기용

int parent,child;

 

 

1. 우선 루트에 있는 값을 어디에다가 저장해놓는다. (리턴이 목적)

    - 끝 원소도 위치를 조정하기 위해 저장해둔다.

    - size 1 감소

 

t = h[1] // 루트에 있는 거 저장해두기 (가장 큰 값)

tmp = h[csize] // 끝원소

cise--;

 

 

2. [ 트리의 가장 아래 + 가장 오른쪽 있는 원소 (=A) ]를 루트자리에 갖다놓는다.

parent = 1 ; //root

child = 2;     //root의 left

 

 

3.  Child가 없으면 A의 위치가 parent 위치에 안착함. (종료 조건)

while(child <= csize) //child가 존재하면

 

 3-1)  A의, left와 right child가 있으면 -> 비교하여 둘 중에서 큰 놈을 저장 (반복)

  if ((child <csize) && (h[child].score < h[child+1].score)) // child가 있고, 오 왼 중에 오른쪽이 더 크면

     child ++; // 오른쪽 child 선택 ( 큰 놈 주소 딱 대기)

  +  왼쪽이 더 크면 어차피 뭐 그 상태니까 굳이 조건문 더 안 만들어도 됨

조건문에서 =<가 아니라 <라는 건 하나 더 여유가 있다는 뜻이니까 그게 오른쪽이 있다는 

 

 3-2) 큰 놈 < A이면, 현 위치에 안착

    if(tmp.score > = h[child].score)    //3-1에서 찾은 큰 놈과 tmp(가장 밑에 있던 원소)를 비교

       break; //A는 이 자리에 있겠다.

 

 3-3) 큰 놈 > A이면, 큰 놈과 자리 큰 놈과 A의 자리를 바꾸고, 큰 놈 원소값을 A원래 자리로 바꾸고

        다시 3-1)부터 반복

         h[parent] = h[child]   //밑에 있는 더 큰 놈을 위로 올림

         parent = child // 한 단계 내려감

         child *=2;        // parent의 밑으로 내려감

 

4. 찾은 위치에 값을 넣는다.

h[parent] = tmp ;

 

5. 가장 처음 리턴하려고 꽁쳐놨던 애를 리턴

return t;

 

 

---

 

무작위 array를 heap으로 바꾸기 (delete 함수와 유사함)

- Constructor 의 parameter로 리스트를 준다.

- root만 잘못된 tree에 대해서 root의 위치만 재조정한다고 생각하면 됨.

 

int tmpkey      // 루트의 점수

int child          // child 노드 둘러보기위한 함수

element tmp  //  둘러보는 주체

+ (parameter로 int t_root를 받음)

 

1) (잘못 설정된) root 원소 저장

2) left child 선택

 

tmp = h[t_root]  // tmp에 root를 넣음

tmpkey = h[t_root].score;  //tmpkey에 root점수를 넣음

child = 2*t_root;  //root의 왼쪽 child

 

3) root를 제대로 자리를 찾아주기 위해 다음을 반복

  3-1) child가 없으면 현위치로 자리 결정

        while(child<=csize)

 

  3-2) left child 와 right child(이건 없을 수도) 를 비교하여 큰 값을 선택하고

          if((child<csize) && (h[child].score < h[child +1].score))

             child++;

       

  3-3) 잘못된 root 와 비교하여 이게 작다? > 현재 위치에 root가 감

            if (tmpkey> h[child].score)

                break;   (while 밖에 현재 자리에 root가 간다는 명령어가 있어서 그냥 나가면 됨)

 

        

  3-4)  잘못된 root 와 비교하여 이게 크다 ? > parent로 큰 자식이 이동, root는 child로 내려감

         후에, 3-1) 부터 다시 반복

           3-3) }else { 

                      h[child/2] = h[child]; //밑에 애가 부모로 올라오고

                      child *=2;                 //child는 내려감

 

 4)  찾은 위치에 잘못된 root 값을 넣는다.

      h[child/2] = tmp;    //parent를 가지고 계산하지 않고, child만 계산하면서 나왔기 때문에  child/2

 

 

 

---

 

임의로 배열된 array -> heap

 

- parameter로 (a[], int원소 개수n)를 받음

  int k;

 

- array는 첫 원소가 0번째이고, heap은 첫 원소가 1번째이기 때문에

   array를 heap의 공간으로 저장한다. (0번째 시작 -> 1번째 시작)

    for (k=1; k<= n; k++)

    h[k] = a[k-1] ;

 

 

- heap의 size는 n

     csize = n; 

 

- 마지막 internal node에서(child가 있는 노드 = leaf가 아닌 노드) (마지막 internal = leaf -1) 시작하여

 역순으로 root까지

- 해당 node를 root로 하는 subtree에 대해 adjust() 수행

 

for(k = n/2 ; k>=1; k--) // internal node에서부터 역순으로 올라가는 걸 나타냄

adjust(k);

 

 

 

 

한동대학교 김호준교수님 - 데이터구조 ppt