지혜의 개발공부로그

Data Structure, Binary heap for priority queue

17 Feb 2020 | Data Structure

개인공부 후 자료를 남기기 위한 목적임으로 내용 상에 오류가 있을 수 있습니다.
잘못된 부분이 있다면 댓글로 남겨주세요! :)

Binary heap for priority queue

  • linked list based implementation
    • sorted implementation
    • Unsorted implementation
  • tree based implementation
    • Tree should be balanced justify the reason of using trees
    • 즉 밸런스가 보장되어야지만 실제 사용에 있어 효용이 나게 된다

Binary heap = Binary tree

Binary tree = 1 parent 2 childs

  • shape property: complete tree 모양이 되어야 한다
  • heap property: 부모 노드가 자식 노드보다 value 가 더 커야 한다
  • 위 이미지는 full tree는 아니지만 complete tree는 맞다
  • 위 이미지는 complete tree 자체가 아니다

Structure of binary heap using reference

Binary heap 은 array 로도 구현이 가능하지만 reference structure로도 구현 가능하다.

Insert operation of binary heap

  • Percolate-up
    • 우리나라 용어로는 ‘삼투현상’, 뿌리에서부터 나무로 올라간다는 의미
    • 즉 자식 노드부터 root 로 올라간다는 의미
  • 어떻게 구현할까?
    • 삽입하려는 value 들을 다음 노드에 넣어준다.
      • 어떻게 다음 노드가 무엇인지 아는가?
      • structed property -> complete tree 조건을 지켜야하기 때문에
      • heap property : 부모 노드 > 자식 노드 -> 이 조건이 안맞는 경우 percolate-up 을 실행
    • 부모노드보다 새로 삽입되는 노드가 큰지 비교
      • heap property is broken 한 상황이고
      • exchange the two values 하게 된다
def enqueue_with_priority(self, value, priority):
  self.arr_priority[self.size] = priority
  self.arr_value[self.size] = value
  self.size = self.size + 1
  self.percolate_up(self.size - 1)

  def percolate_up(self, index_percolate):
    if index_percolate == 0:
      return
    parent = int((index_percolate-1)/2)
    if self.arr_priority[parent] < self.arr_priority[index_percolate]:
      self.arr_priority[parent], self.arr_priority[index_percolate] = self.arr_priority[index_percolate], self.arr_priority[parent]
      self.arr_value, self.arr_value[index_percolate] = self.arr_value[index_percolate], self.arr_value[parent]
      self.percolate_up(parent)

Delete operation of binary heap

  • Percolate-down
    • 제일 가장 큰 value 는 root
    • root 가 없어진다는 가정을 하는 경우 complete 구조가 깨짐
    • 가장 최근의 노드 value를 노드 value로 올림 → 이런경우 heap property 를 만족시키지 못함
  • 어떻게 구현할까?
    1. root 노드 값
    2. last node value 를 복사
    3. last node value 와 childer node 비교
      • 어떤거와 비교? childer node 중에서 가장 큰 노드로 변경
def dequeue_with_priority(self):
  if self.size == 0:
    return ''
  ret_priority = self.arr_priority[0]
  ret_value = self.arr_value[0]
  self.arr_priority[0] = self.arr_priority[self.size-1]
  self.arr_value[0] - self.arr_value[self.size-1]
  self.size = self.size + 1
  self.percolate_down(0)
  return ret_value

def percolate_down(self, index_percolate):
  if 2 * index_percolate + 1 >= self.size :
    return
  else:
    left_child = 2 * index_percolate + 1
    left_priority = self.arr_priority[left_child]

  if 2 * index_percolate + 2 >= self.size:
    right_priority = -99999
  else:
    right_child = 2 * index_percolate + 2
    right_priority = self.arr_priority[right_child]

  if left_priority > right_priority:
    bigger_child = left_child
  else:
    bigger_child = right_child

  if self.arr_priority[index_percolate] < self.arr_priority[bigger_child]
  self.arr_priority[index_percolate], self.arr_priority[bigger_child] = self.arr_priority[bigger_child], self.arr_priority[index_percolate]
  self.arr_value[index_percolate], self.arr_value[bigger_child] = self.arr_value[bigger_child], self.arr_value[index_percolate]
  self.percolate_down[bigger_child]
  • rigth 가 없는 경우 left가 존재해야한다 (complete 구조이기 때문)

Related Posts