알고리즘 힙

힙

최솟값 또는 최댓값을 빠르게 찾아내기 위해 완전이진트리 형태로 만들어진 자료구조

최대 힙

부모 노드 값이 자식 노드의 값보다 크거나 같음

최소 힙

부모 노드 값이 자식 노드의 값보다 작거나 같음

완전이진트리

마지막 레벨 직전의 트리까지 모든 노드들이 채워져 있어야 하고, 마지막 레벨에서는 노드들이 다 채워져 있지 않아도 되지만, 왼쪽부터 오른쪽 방향 순으로 채워져 있어야 한다.

힙 구현

배열로 구현, 인덱스0은 사용하지 않음

부모/자식 사이의 인덱스 관계

인덱스 i의 부모인덱스 : i/2
인덱스 i의 왼쪽 인덱스 : i*2
인덱스 i의 오른쪽 인덱스 : (i*2)+1

힙 연산

삽입 연산

1) 마지막 위치에 노드 만들어 삽입
2-1) 부모 노드보다 값이 작으면 끝
2-2) 부모 노드보다 값이 크면 부모노드와 스위치
3) 2번 과정 최대 루트까지 반복

삭제 연산

1) 루트 노드 값 제거
2) 마지막 노드 값 루트로 옮기고 노드 삭제
3-1) 자식 노드보다 값이 크면 끝
3-2) 자식 노드보다 값이 작으면 스위치
4) 3번 과정 최대 리프까지 반복

참고자료
https://velog.io/@suk13574/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0Java-%ED%9E%99heap

https://st-lab.tistory.com/205