heaport에 대해 heapify를 사용하여 힙을 두 개의 하위 힙으로 나누는 방법은 무엇입니까?

Question

필자는 triyng을 사용하여 Python에서 HeapSort 함수를 작성하고 몇 가지 보조 함수를 사용합니다.

는 는

내 책 지침을 따르려고 노력하고, 노드가있는 힙의 올바른 순서를 복원 fixHeap처럼 다음되지 규칙 일부 기능을 사용하고 있습니다 : 이제

def getMaxKnot(i,j,A): 
    k = max(A[i],A[j]) 
    if k==A[i]: 
     return i 
    if k==A[j]: 
     return j 


def fixheap(v,H): #basically restore an heap with a node not following heap rules 
    if (2*v+1)>len(H)-1: 
     return H 
    else: 
     u=getMaxKnot(2*v+1,2*v+2,H) 
     if H[u]>H[v]: 
      listoperations.swap(u,v,H) #swap item in position u and v 
     return fixheap(u,H) 

, 난을 만들 기본적으로 원하는 왼쪽 트리 및 오른쪽 트리에서 재귀 적으로 작동하는 함수 heapify. fixheap 함수를 사용하여 올바른 순서로 복원합니다.

내 생각이었다 다음

def heapify(A): 
     if A==[]: 
      return A 
     else: 
      heapify(LEFT TREE) 
      heapify(RIGHT TREE) 
      fixheap(0,A) 

LEFT TREE 우 트리로 내 배열 A를 분할하는 방법에 어떤 아이디어가?

Answer 1

먼저 fixheap에 누락 된 것이 있습니다. 노드 v이 012.배열의 끝을 넘어 서기 때문에 getMaxKnot이 잘못된 색인 오류를 유발한다는 것을 상상하십시오.

개인적으로, 나는 getMaxKnot이 별도의 기능을 수행 할 가치가 없다고 생각합니다. 또한 fixheap 인수를 반대 순서로 두어 두 번째 요소를 쉽게 생략하고 기본값을 부여 할 수 있습니다 (루트 요소 인 경우). 또한 정말 한 줄을 두 값입니다 교환 :

def fixheap(H, v = 0): # put arguments in this order 
    u = 2*v + 1 
    if u >= len(H): 
     return H 
    if u+1 < len(H) and H[u+1] > H[u]: # Only compare when there are two child nodes 
     u += 1 
    if H[u] > H[v]: 
     [H[u], H[v]] = [H[v], H[u]] # Swapping is easy 
     return fixheap(H, u) 

을 다음 주 질문 : 당신의 heapify 또한 heapify 할 서브 트리의 루트 것 인수로 노드를 받아야합니다.

는 'ausiliar 기능'이란

def heapify(H, v = 0): 
    u = 2*v + 1 
    if u >= len(H): 
     return H 
    heapify(H, u) 
    if u + 1 < len(H): # make sure there is a right child 
     heapify(H, u+1) 
    fixheap(H, v)