Binary Heaps
최소값, 최대값을 구하는 연산을 빠르게 하기 위해 고안된 완전 이진 트리를 기본으로한 자료구조.
Min heap
작은 값이 항상 루트.
O(logN)의 시간 복잡도.
최소힙에 노드 삽입하기
맨 아래 레벨의 왼쪽부터 추가함 -> 자신의 부모노드와 비교해서 작으면 자리 바꿔가며 타고 올라가서 루트에 최소값이 오게 함.
최소힙에서 값 꺼내오기
최소값 (루트)에서 꺼내온다. 그러려고 만든 것이니까.
-> 꺼낸 뒤에는 루트가 빔 -> 맨 마지막 노드를 가져와서 루트에 채움 -> 자신의 자식노드와 비교해서 작은 값을 바꿔가며 타고 내려가서 루트에 최소값이 오게 함.
Max heap
Max heap
