TIL-231002(자료구조 & 알고리즘 2주차)

📝오늘 공부한 것

• 프로그래머스 문제풀기
• 스파르타코딩클럽 자료구조 & 알고리즘 2주차 강의 듣기

 

알게 된 점❗

[  최대 힙  ]

Heap(힙)

• 데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 완전 이진 트리
• 항상 큰 값이 상위 레벨에 있고 작은 값이 하위 레벨에 있도록 하는 자료구조
• 부모 노드의 값이 자식 노드의 값보다 항상 커야 한다.
• 그렇게 되면 가장 큰 값은 모든 자식보다 커야 하기 때문에 가장 위로 간다. 따라서 최대의 값들을 빠르게 구할 수 있다.
• 최댓값이 맨위인 힙을 Max Heap, 최솟값이 맨 위인 힙은 Min Heap이라고 한다.

 - 이진트리와는 다르게 좌, 우 자식의 위치가 대소관계를 반영하지 않는다.

 - 계산 편의를 위해 인덱스는 1부터 사용한다.

 

최대 힙 - 삽입 알고리즘

합의 규칙 : 힙은 항상 큰 값이 상위 레벨에 있고 작은 값이 하위 레벨에 있어야 한다.

따라서, 원소를 추가할 때는

1. 원소를 맨 마지막에 넣는다.

2. 부모 노드와 비교한 뒤 더 크다면 자리를 바꾼다.

3. 부모 노드보다 작거나 가장 위에 도달하지 않을 때까지 2.과정을 반복한다.

 

최대 힙 - 삽입 시간복잡도

완전 이진트리의 최대 높이는 O(log(N))이고, 반복하는 최대 횟수도 O(log(N)) 이다.

즉, Max Heap의 원소 추가는 O(log(N)) 만큼의 시간 복잡도를 가진다고 분석할 수 있다.

 

최대 힙 - 추출 알고리즘

최대 힙에서 원소를 추출하는 방법은 최댓값, 루트 노드를 삭제하는 것이다.

스택과 같이 맨위에 있는 원소만 제거할 수 있고, 다른 위치의 노드를 삭제할 수 없다.

따라서, 원소를 삭제할 때는

1. 루트 노드와 맨끝에 있는 원소를 교체한다.

2. 맨 뒤에 있는 원소를 (원래 루트 노드)를 삭제한다.

3. 변경된 노드와 자식 노드들을 비교한다. 두 자식 둥 더 큰 자식과 비교해서 자신보다 자식이 더 크다면 자리를 바꾼다.

4. 자식 노드 둘 보다 부모 노드가 크거나 가장 바닥에 도달하지 않을 때까지 3. 과정을 반복한다.

5. 2에서 제거한 원래 루트 노드를 반환한다.

 

최대 힙 - 추출 시간복잡도

완전 이진트리의 최대 높이는 O(log(N))이고, 반복하는 최대 횟수도 O(log(N)) 이다.

즉, Max Heap의 원소 삭제는 O(log(N)) 만큼의 시간 복잡도를 가진다고 분석할 수 있다.