Heap

• stack : LIFO
• queue : FIFO
• priority queue : 가장 우선순위가 높은 데이터부터 출력
  • 네트워크 트래픽 제어, os에서 작업 스케줄링
  • 배열, 연결리스트, 힙으로 구현가능하나 힙이 제일 효율적

특징

• 우선순위 큐를 위해 만들어진 자료구조
• 최댓값, 최솟값을 빠르게 찾아내도록 만들어진 자료구조
• 중복값 허용

종류

• max heap: 부모 >= 자식, 완전 이진 트리(왼쪽부터 차례대로 채워져있는 트리)
• min heap: 부모 <= 자식, 완전 이진 트리

max heap 에서 부모와 자식과의 index 관계

• left child = parent * 2
• right child = parent * 2 + 1
• parent = child / 2

삽입

1. 힙의 마지막 노드에 삽입
2. 재구성

삭제

1. 루트 노드 삭제
2. 삭제된 루트 노드 자리에 마지막 노드를 넣음
3. 재구성

 

References

https://github.com/gyoogle/tech-interview-for-developer

GitHub - gyoogle/tech-interview-for-developer: 👶🏻 신입 개발자 전공 지식 & 기술 면접 백과사전 📖