알고리즘을 하려면 이런 것 구현은 스스로 해야한다고 해서 Python을 통해서 구현해 봤다.
먼저 MaxHeap에 대해서 말하자면!
인터넷에서 찾아본 말로는
각 최대트리면서 완전이진트리
각 노드의 키값이 그 자식의 키값보다 작지않은 트리이다.
한마디로
최대값(?) 순으로 정렬된 완전이진트리라는 말이다.
아예 배열이 최대값이라는 말은 아니고
부모노드는 자식노드보다 작지만 않으면 된다.
목적은 가장 큰 값을 빠르게 찾기 위한 것!
Heap이라는 완전 이진트리의 배열 안에 어떠한 원소를 집어넣는 순간 촤르륵 하면서 배열이 정렬되는 것이 MaxHeap이다.
사실 이해는 했는데 개념을 멋있게 설명을 못하겠음;;
인터넷에 맛깔나게 설명한거 있으니까 그거를 찾아보셈용;;
왜냐하면 이 블로그를 쓰는 이유는 내가 생각하기에 혼자힘으로 으쌰으쌰 풀어내서 기분좋아서 쓰는거니까 ㅎ;
MaxHeap
처음에는 그냥 조빱인줄 알았다.
그래서 간단하게 생각한 것이
1. 추가 (insert)
생각의 회로에 대해서 말하자면
1. 자신의 부모와 비교
2. 자신이 더 크다면 위치 change
3. 바뀐 위치에서 또 부모 확인 -> 반복
여기서 생각해야 할 점이
"언제까지 부모교체(하극상)을 해야하는가?"" 이다.
- 부모보다 값이 작은경우 -> 하극상을 할 필요가 없다.
이런건 중간에 break나 return을 넣어주면 되지만, 결국은 제일 큰 값이 들어오게 되면 왕(루트)가 교체되어야 하는게 아닌가?
그래서 생각을 한게
"추가된 값의 인덱스의 값이 0이 될때까지 반복" 이 내가 생각한 키워드다.
import sys
input = sys.stdin.readline
# x가 자연수라면 배열에 x라는 값을 넣는 연산!!
n = int(input())
heap = []
heap_ptr = 0
def insert(n):
global heap_ptr
heap.append(n)
# idx : 추가한 노드의 위치를 나타낸 것 / 그래서 처음값은 맨끝으로 설정
idx = heap_ptr
heap_ptr += 1
# while 조건 : insert를 한다면 결국 루트까지는 가야한다는 것
while idx != 0:
# 부모와 비교해서 부모보다 크다면 값을 바꾸고
if heap[idx] > heap[(idx-1)//2]:
temp = heap[idx]
heap[idx] = heap[(idx-1)//2]
heap[(idx-1)//2] = temp
# idx를 재설정해줌
idx = (idx-1)//2
else:
return
return여기서 핵심적인 키워드는 idx != 0이다.
끝까지 간다 이말이야~
idx = (idx-1)//2 를 통해서 idx를 재설정을 해주고
그리고 나는 0부터 시작하는 배열로 만들었기 때문에 부모노드는 (idx-1)//2의 인덱스는 다들 아실테고
사실 insert는 구현하기가 그렇게 어렵지 않았음
delete가 지랄맞아서 문제였음!
2. 삭제 (delete)
maxheap의 삭제과정을 보면 아시겠지만, 뭐 이따구로 삭제를 하나 싶다. 하지만 빨랐죠?
1. 맨 윗놈을 제거 (젤 큰수임)
2. 맨 밑에있는 애가 그 자리로 들어오게 됨
3. 그러면 그 자식들 중 가장 큰애와 비교
4. 만약 자식보다 작다면 위치change
이렇게 생각했다.
그리고나서 여기서도 들었던 하나의 생각
언제까지 하는가?
그러면서 고려했던게 너무 개빡침
먼저 나는 배열을 통해 구현했기 때문에 자식놈들을 확인했어야 했기 때문에 특정 인덱스를 n이라 할 때 자식노드의 인덱스는 2n+1, 2n+2이다.
근데 만약에 자식이 없는 경우는 어떡하는가?
리스트 범위를 벗어났다고 지랄지랄 왈왈
여기서 멘붕이 왔다.
하지만 이겨냈다
처음에 생각했던건, 머릿속에서 생각만 했던건!
geeks for geeks에서 가져왔음!
https://www.geeksforgeeks.org/max-heap-in-java/
저런 경우 힙의 길이가 있지 않겠는가?
하지만 logN만큼만 비교를 해주면 되는 것이다.
추가되는 수(테스트 케이스의 범위)는 2^31승이기 때문에 21억! 이기 때문에 로그를 취해주면 30 언저리가 나오기 때문에 결국에 최대 31번? 정도밖에 비교를 안하는 것이다.
아무튼 여기까지밖에 생각을 안했는데.... 누가 좀 알려줘~!
다시 돌아와서
내 생각에는 아까 insert에서 썼던 아이디어를 참고해서
결국은 idx가 잎노드가 되면 끝나면 되는거다!!
완전이진트리에서 잎노드가 시작되는 인덱스 : 길이//2
결국에 idx가 길이//2 <= idx < 길이 가 되면 되는 것!
자 드가자~~
.
.
.
하지만 내 생각은 개쳐망했다!
왜냐면
내가 그린그림이다.
이새~~~끼가 문제다!
왼쪽밖에 비교를 안하니 또 list error가 뜨는거있지
하지만 애도 결국에는 한 리스트에 1번밖에 존재하지 않는다.
그것도 배열의 길이가 짝수 + 비교해야 할 노드의 위치 = (배열의 길이//2 -1) 인 경우에 말이지
그래서 그것도 그냥 조건으로 추가해줬다. 호호
또 생각해야 할게
자식들끼리도 서열이 있지 않겠는가?
왼쪽자식과 오른쪽자식중에 큰놈하고 바꿔야한다;; ㅜㅜ
아무튼 그 조건까지 고려해서 코드를 추가해주면!
def delete():
global heap_ptr
if len(heap) == 0:
return 0
if len(heap) == 1:
heap_ptr -= 1
a = heap.pop(0)
return a
ret = heap[0]
heap[0] = heap.pop()
# length : 배열의 길이 -> 왜냐? 완전이진트리이기 때문에
# 배열의 길이가 정해진다면 단말노드의 범위가 정해짐
length = len(heap)
heap_ptr -= 1
idx = 0
while True:
# 그래서 밑에 if 조건에 따라 idx가 단말노드의 범위 안에 들게된다면 조건을 만족하고 나오게 된다는 것
if length//2 <= idx < length:
return ret
# 자식노드가 왼쪽만 있는 경우임
if length%2 == 0 and idx == ((length//2)-1):
if heap[idx] < heap[2*idx +1]:
temp = heap[idx]
heap[idx] = heap[2*idx+1]
heap[2*idx+1] = temp
idx = 2*idx +1
else:
return ret
else:
# 왼쪽이 더 큰경우
if heap[2*idx +1] > heap[2*idx+2]:
if heap[idx] < heap[2*idx +1]:
temp = heap[idx]
heap[idx] = heap[2*idx+1]
heap[2*idx+1] = temp
idx = 2*idx +1
else:
return ret
else:
if heap[idx] < heap[2*idx +2]:
temp = heap[idx]
heap[idx] = heap[2*idx+2]
heap[2*idx+2] = temp
idx = 2*idx +2
else:
return ret코드가 넘나리 더럽습니다.
양해좀;;
아무튼 배열이 0일때는 0으로 보내줘야 하는 백준의 규칙과
1일때는 그냥 없애버리면 되기 때문에 저렇게 해줬고
나머지는 코드 보시면 됨당
전체코드
# https://www.acmicpc.net/problem/11279
import sys
input = sys.stdin.readline
# x가 자연수라면 배열에 x라는 값을 넣는 연산!!
n = int(input())
heap = []
heap_ptr = 0
def insert(n):
global heap_ptr
heap.append(n)
# idx : 추가한 노드의 위치를 나타낸 것 / 그래서 처음값은 맨끝으로 설정
idx = heap_ptr
heap_ptr += 1
# while 조건 : insert를 한다면 결국 루트까지는 가야한다는 것
while idx != 0:
# 부모와 비교해서 부모보다 크다면 값을 바꾸고
if heap[idx] > heap[(idx-1)//2]:
temp = heap[idx]
heap[idx] = heap[(idx-1)//2]
heap[(idx-1)//2] = temp
# idx를 재설정해줌
idx = (idx-1)//2
else:
return
return
def delete():
global heap_ptr
if len(heap) == 0:
return 0
if len(heap) == 1:
heap_ptr -= 1
a = heap.pop(0)
return a
ret = heap[0]
heap[0] = heap.pop()
# length : 배열의 길이 -> 왜냐? 완전이진트리이기 때문에
# 배열의 길이가 정해진다면 단말노드의 범위가 정해짐
length = len(heap)
heap_ptr -= 1
idx = 0
while True:
# 그래서 밑에 if 조건에 따라 idx가 단말노드의 범위 안에 들게된다면 조건을 만족하고 나오게 된다는 것
if length//2 <= idx < length:
return ret
# 자식노드가 왼쪽만 있는 경우임
if length%2 == 0 and idx == ((length//2)-1):
if heap[idx] < heap[2*idx +1]:
temp = heap[idx]
heap[idx] = heap[2*idx+1]
heap[2*idx+1] = temp
idx = 2*idx +1
else:
return ret
else:
# 왼쪽이 더 큰경우
if heap[2*idx +1] > heap[2*idx+2]:
if heap[idx] < heap[2*idx +1]:
temp = heap[idx]
heap[idx] = heap[2*idx+1]
heap[2*idx+1] = temp
idx = 2*idx +1
else:
return ret
else:
if heap[idx] < heap[2*idx +2]:
temp = heap[idx]
heap[idx] = heap[2*idx+2]
heap[2*idx+2] = temp
idx = 2*idx +2
else:
return ret
for i in range(n):
k = int(input())
if k == 0:
print(delete())
print(f"heap : {heap}")
else:
insert(k)
print(f"heap : {heap}")사실 이걸 누가 볼거라고는 생각안함;
왜냐면
1. 어려워서 백준풀이 보러온사람
: 에잇 ~~ 싰팔 블로그 글이 왜 이따구야
하면서 나갈게 뻔함;;
2. 다른 사람 풀이는 어떤가 궁금해서 들어온 사람
: 위와 동일
3. 어쩌다 이상한 루트로 들어온 고인물
: 절대 안볼것같음ㅋㅋ
그냥 기록하고싶어서 해논거임!
그렇지만 괜스레 누가 왔으면 싶어서 태그도 여러개 해놨음!
ㅋㅋㅋㅋ글 재밌게봤습니다.! 수고하셨네요 ㅠ