[자료구조] heap in FEMU

Goal

• priority queue를 타겟으로 만들어진 자료구조, heap에 대한 이해
• FEMU 상에서 heap이 어떻게 구현되어 있는지 확인
• heap의 삽입과 삭제를 이해

사전 지식

• priority queue: priority의 개념을 queue에 도입한 자료구조
  • data들이 priority를 가지고 있고 priority가 높은 data가 먼저 나간다.
    
  • priority queue의 사용 예시로는
    1. 시뮬레이션 시스템
    2. 네트워크 트래픽 제어
    3. operating system에서의 작업 스케쥴링
    4. 수치 해석적인 계산이 있다.
  • priority queue는 배열, 연결리스트, heap으로 구현 가능하다. 이 중에서 heap으로 구현하는 것이 가장 효율적인 것으로 알려져있다.
    

자료구조 'heap' 이란

• complete binary tree의 일종으로 priority queue를 위해 만들어진 자료구조이다.
• 여러 개의 값들 중에서 최댓값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조
• heap은 반정렬 상태를 유지한다.
  • 큰 값이 상위 레벨, 작은 값이 하위 레벨
  • 간단히 말하면 parent node의 key가 child node의 key보다 항상 큰/작은(조건에 따라 다름) binary tree를 말한다.
• heap tree에서는 중복 값을 허용한다.
• 예시
  
  
• 위의 그림에서 index 3에 해당하는 parent node에서 child node로 접근할 때는
  parent node의 index x 2 = left child_node 의 index
  parent node의 (index x 2) + 1 = right child_node 의 index를 가리키게 되므로 이렇게 접근을 하게 된다.

heap에서의 insert

1. heap에 새로운 요소가 들어오면, 마지막 index에 insert node로 삽입한다.
2. insert node가 parent node들과 교환해서 heap의 성질을 만족시킨다.
   

heap에서의 remove(pop)

1. priority queue에서는 priority가 가장 높은 root node를 pop시키기 때문에 root node를 pop하고 그 자리에 마지막 index node를 삽입한다.
2. 그 다음 child node와의 비교를 통해 tree를 재정렬한다. (완전 정렬이 아닌 반정렬 상태가 된다.)
   

• 위의 그림에서 마지막 index node를 root node의 자리로 삽입하고 아래의 child node와의 비교를 통해 정렬을 한다.
• 아래는 femu에서 victim line을 선정할 때 사용되는 code로 root node로 마지막 node가 삽입된 후 정렬하는 code이다.
  
• i 는 index로 이전 함수로 부터 1의 값을 받는데 그것은 root node의 위치를 가리킨다.
• left 함수는 #define left(i) ((i) << 1) 로 정의 되어 있다. 이를 통해 child node의 index를 찾아갈 수 있다.
• 두 번째 if 문에서 조건을 보면 right child node가 존재하고 left child와 right child의 priority를 비교해서 right child의 priority가 더 높으면 child_node 변수에 +1을 해서 right child node의 값을 사용하게 되는 code였다.