Heap Operations

• Heaps

  • Shape : complete binary tree
  • Order : parents value > child value

• Heap Operations

  • Insert a New Node
    1. 아랫줄 가장 왼쪽에 new element 넣기
    2. ReheapUp 부르기

• Heap이 왜 필요한가

  • largest value는 항상 root에 있음
  • heap에서 maximum, minimum value O(1)에 찾을 수 있음

Priority Queue

• 우선순위 큐 (heap으로 구현)

  • highest-priority element를 어느 시간에나 접근할 수 있는 ADT
  • ex. CPU task queue
  • immediate processing이 필요한 테스크에 higher priority 부여

• Get (remove) a largest value

  1. 밑에서 가장 오른쪽 아이템을 루트로 복사
  2. 밑에서 가장 오른쪽 아이템을 삭제
  3. Fix the heap by calling ReheapDown
     1. child > parent 인 경우 노드 swap

Graph

• Graph

  • vertices와 edge들로 구성
  • G = (V,E)
  • V(G) : set of vertices
  • E(G) : set of edges (pair of vertices)

• Undirected Graph

  • edge가 방향이 없음