달력

062018  이전 다음

  •  
  •  
  •  
  •  
  •  
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30

'힙'에 해당되는 글 1건

  1. 2010.12.02 [Algorithm] Binary Heap

Heap이란 ? complete binary tree이고, 부모노드는 항상 자식노드보다 크거나 같음을 만족하는 자료구조이다.

 

출처: http://code.cloudkaksha.org/binary-tree/types-binary-tree

위 사진은 binary tree의 3가지 타입을 보여준다.

full binary tree는 잎 노드를 제외한 노드들의 자식 노드가 0개 혹은 2개인 트리를 말한다.
complete binary tree는 마지막 level을 제외한 모든 level에 노드가 채워져있고 마지막 level은 최소한 왼쪽으로 노드가 채워진 트리를 말한다. 
perfet binary tree는 잎노드를 제외한 모든 노드들의 자식노드가 2개인 트리를 말한다. 노드의 갯수는 2^n-1개 있다.(n은 마지막 level)

앞에서 본것처럼 Heap에는 max heap과 min heap이 있다.
이름에서도 알수 있듯이, max heap은 현재 저장하고 있는 값중 가장 큰 값을 root에 위치시키고,
min heap
은 가장 작은 값을 root에 위치시키는것을 말한다.

max heap
의 삽입, 삭제 과정을 보자.

<<<<<<<<<<<<<<<<<<<<
삽입>>>>>>>>>>>>>>>>>>>>>>>>
삽입 시 제일 마지막 노드에 추가후,
부모노드보다 추가된 노드의 키값이 크면, 바꾼다.(min heap은부모노드보다 작으면 바꿈)




<<<<<<<<<<<<<<<<<<<<
삭제>>>>>>>>>>>>>>>>>>>>>>>>

삭제된 노드를 채우기 위해서 마지막 level의 가장 오른쪽 노드를 삭제할 노드로 이동시킨 후,
자식노드와 비교하면서 Heap을 재구성 한다.

 검색에 Heap을 쓴다고해서 공부해 봄 . . .


Posted by 오산돌구