글 읽기 - max heap에서 원하는 위치 값 삭제

yukariko 9년 전 0

max heap에서 원하는위치의 값을 제거하려했는데 뜻대로 잘안되는군요.. 일반적인 알고리즘에서

루트를 pop해주듯이 루트대신 원하는 위치로 바꿔서 구현하면 안되는건가요?

제가 참고한 서적엔 그렇게 나와있어서 max힙을 구현하고 거기서 최솟값을찾아 그위치를 제거하도록 해줬는데 틀림이 떠서요..

결국 max힙 min힙을 둘다구현해줬는데 제가 말한 방법에 문제가 있는건가요?

yukariko 9년 전 0

그것은 그냥 루트노드를 없엘 때 하는 방법아닌가요?

제가 물어본것은 루트가 아니라 원하는 위치를 제거하는 방법인데

말씀하신 방법을 위치만 바꿔서 똑같이 구현해주니 틀림이 떠서 질문한것입니다.

jng6017 9년 전 0

위치만 바꿔서 한다해도 구현에 딱히 문제는 없을듯한데...

저도 잘 모르겟네요 죄송합니당..

pl0892029 9년 전 1

max-heap에서 minimum element를 찾는걸 O(logN)만에 가능한가요??

heap 구조는 상하 비교라서 minimum을 찾으려면 제일 밑의 원소들을 살펴봐야하기 때문에 O(N) 혹은 O(NlogN)이 걸리는 걸로 알고 있습니다.

원하는 위치를 제거하는 연산 자체는 아무런 문제 없습니다. (sub-heap 역시 heap의 규칙을 모두 만족하고 있기 때문에)

yukariko 9년 전 0

네 최솟값찾는건 제가짠건그냥 선형비교로했구요 원하는위치제거도 말씀하신것처럼 구현햇는데 자꾸오답이 떠서요

힙구조자체에 문제가있엇다면 max min들다 구현해준것도 틀려야맞으니 문제는없어보입니다만..

yukariko 9년 전 1

전체 소스를 보여드리긴 너무 복잡할거같고 루트 제거 함수를 가져와봤습니다.

원하는 위치 제거는 저기에서 0을 전부 인자 i 로 대체한거구요.

hPercolateDown(h,0);

이 함수는 힙 위치 조정하는 함수입니다.

hDATA hDeleteTop(Heap *h)
{
  hDATA data;
  if(h->count==0)return -1;
  data=h->arr[0];
  h->arr[0]=h->arr[h->count-1];
  h->count--;
  hPercolateDown(h,0);
  return data;
}

yukariko 9년 전 0

아.. Down Heap이 아니라 UpHeap을 해줘야 하는군요

제가 이해를 잘못해서 생긴 문제였네요.

답변 감사합니다!

댓글을 작성하려면 로그인해야 합니다.