heap에서의 자료 갱신 관련 질문 killerna 안녕하세요. 보통 heap에서 자료 수정을 할때 정말 수정을 하거나(보통 직접 구현한 경우) 아니면 수정한 값을 하나 더 넣고 업데이트 하거나 하는 것으로 알고있는데요. heap중에서도 binary heap을 구현했다고 가정하고 그중에 전자(그러니까 직접 구현한 경우)에 값 수정을 log n에 하려 하면 (물론 n은 자료 수) (heap의 해당 값의 위치가 a일때) 1. a의 위치를 루트로 하는 heap 구성 (자식 2개 비교해나가면서 아래로) 2. a의 위치에서부터 자신의 부모를 타고 올라가면서 갱신(가능할때까지) 순서로 하는걸로 알고 있는데, 제가 알고 있는게 예외가 있는지 갑자기 궁금해지기 시작해서 글을 올립니다. (평상시엔 별로 신경 안쓰고 있던 부분인지라..) 틀리거나 빼먹은게 있다면 어디가 문제인지 좀 알려주세요.. 감사합니다. (맞으면 맞다고 알려주셔도 감사합니다;;) 12년 전
4개의 댓글이 있습니다. JongMan 질문이 잘 이해가 안가는데, min-heap 의 경우 힙에 들어 있는 원소의 크기를 줄이기 위해서는 해당 위치를 먼저 찾은 뒤 min-heap 의 조건을 충족할 수 있도록 부모와 비교해서 위로 올리는 작업을 반복하면 되겠죠. 그럼 1번은 왜 들어가 있는 걸까요? 12년 전 link killerna 아아.. 쉽게 줄이면. (binary) min-heap 을 구성한다고 할때 힙에 들어있는 원소 중 non-root/non-leaf인 원소를 수정하는 경우 min-heap의 조건을 충족하도록 하려면 어떻게 해야하는가? 입니다. 제 생각에 1이 필요한 이유는 min-heap 해당 원소 값을 바꿨을때 자식들(leaf)보다 수정된 값이 더 큰걸로 바뀌게 되면 자기 자식놈이랑 교체해나가는걸 해야 하기 때문입니다. (반대로 위로 올라가는건 그야말로 min 값 후보군이 될 수도 있으니까 당연하구요) 12년 전 link JongMan 아, decrease-key 인줄 알았다능... 뭐 그러면 상관없지 않을까요? 12년 전 link killerna 아 이 방법이 맞나보네요. (얼추 맞는거 같긴 한데) 맞는지 틀린지 확신이 안서서 궁금해서 글을 적었는데.. 답변 감사합니다 '_' 12년 전 link 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
killerna
안녕하세요.
보통 heap에서 자료 수정을 할때
정말 수정을 하거나(보통 직접 구현한 경우)
아니면 수정한 값을 하나 더 넣고 업데이트 하거나
하는 것으로 알고있는데요.
heap중에서도 binary heap을 구현했다고 가정하고
그중에 전자(그러니까 직접 구현한 경우)에
값 수정을 log n에 하려 하면 (물론 n은 자료 수)
(heap의 해당 값의 위치가 a일때)
1. a의 위치를 루트로 하는 heap 구성 (자식 2개 비교해나가면서 아래로)
2. a의 위치에서부터 자신의 부모를 타고 올라가면서 갱신(가능할때까지)
순서로 하는걸로 알고 있는데,
제가 알고 있는게 예외가 있는지 갑자기 궁금해지기 시작해서 글을 올립니다.
(평상시엔 별로 신경 안쓰고 있던 부분인지라..)
틀리거나 빼먹은게 있다면 어디가 문제인지 좀 알려주세요..
감사합니다.
(맞으면 맞다고 알려주셔도 감사합니다;;)
12년 전