원소가 삭제된 후에 해야 할 일은,
1. 가장 마지막 인덱스의 원소를 1번 인덱스 위치로 옮기고
2. 그 원소가 제 자리를 찾을 때까지 아래로 내려야 하는데,
이 코드에서는 다음 마지막 원소를 위로 올리려고 하고 있습니다. 지금 자기 위치를 못 찾은 건 1번 위치에 올라간 원소이고, 다음 마지막 원소는 아무런 상관이 없습니다.
아래와 같은 경우를 생각해 보세요.
11279번 - 최대 힙
감사합니다. 최하위원소를 옮긴후 그대로 sorting하는 매커니즘을 착각을 했네요. 추가할때랑 뺄때랑 같은줄알고 ㅠㅠ pop함수를 그대로 지워버려서 ㅠㅠ 감사합니다!!
댓글을 작성하려면 로그인해야 합니다.
dlwjddls0130 1년 전
먼가 근본적으로 heapify하는 부분에서 잘못된거같은데 잘모르겠습니다.
최대힙이라서 부모노드를 크게 하고, 배열을 사용하고 인덱스는 1~N까지 입니다.
그래서 인덱스가 1이면 더이상 heapify할필요가없기때문에 return했구요.
배열 원소는 삭제가 안되서 인덱스를 둬서 나중에 원소가 삽입되면 덧씌워서 지워가는 방식으로 대입하는걸로 했습니다.
어느 부분을 고쳐야할까요?