진 힙 및 최소 중심의 우선 순위 큐의

Question

누군가가 나에게 말할 수있는이 있습니다 이진 힙의 (최대) 및 이들의 최소 우선 순위 큐의 중심, 그리고 왜/왜 안 그렇습니까? 내가 여기에 사진을 게시하는 방법을 알고하지 않기 때문에 내가 배열에서 그들을 게시 할 것이다,는 x의의는 그 자리가 비어 있음을 의미한다. 여기

우리가 갈 : [8,6,7,4,6,6, X], [4,5,4,7,8,4,6], [4,4,5,7, X, X, 6]

첫 번째는 바이너리 힙, 그리고 다른 두 최소 중심의 우선 순위 queue's 있지만 솔루션에 따라 내가 잘못 있다고 나는 생각한다. 해결책이 잘못되었을 수 있습니다. 어떤 것이 있는지 알고 계시다면 제게 설명해주십시오.

미리 감사드립니다.

Answer 1

음, 첫 번째 바이너리 최대 힙이 될 수 있습니다.

  8 
     6  7 
    4 6 6 

두 번째는 이진 분의 힙입니다 :

  4 
     5  4 
    7 8 4 6 

이 세 번째 바이너리 힙 될 수 없다, 그것은을 준수하지 않기 때문에 그 나무는 다음과 같이 보일 것입니다 모양 속성. 즉, 다음과 같습니다.

  4 
    4  5 
    7 x x 6 

이진 힙에서는 맨 아래 행이 왼쪽으로 채워집니다. 이 나무는 아직 채워지지 않았습니다.

은 그래서 첫 번째 이진 최대 힙입니다. 두 번째는 이진 min 힙이며 min 지향 우선 순위 큐로 볼 수도 있습니다. 나는 세 번째 것을 부를 무엇을 해야할지 모른다. 유효한 최소 힙이 아니며 최소 우선 순위 대기열을 순차적으로 표현한 것은 아니기 때문에 7이 먼저 오기 때문에 6이됩니다.

적어도 바이너리 힙 및 우선 순위 대기열에 대한 필자의 대답을 기반으로 한 대답입니다.