Реализация Min Heap с использованием Python - PullRequest
Новая
       6

Реализация Min Heap с использованием Python

1 голос
/ 19 января 2020

Ниже приведен код, который я написал для выполнения сортировки кучи целых элементов списка. Однако конечный результат не приходит должным образом, так как он должен отсортировать список в минимальном порядке.

Также, кто-то может помочь объяснить сложность этого конкретного кода. 

class Heap:
    def __init__(self):
        self.heap=[]

    def insert(self,num):
        self.heap.append(num)

    def printHeap(self):
        print(self.heap)


    def heapify(self, index):

        size=len(self.heap)-1

        left=2*index+1   #calculating Left Node
        right=2*index+2  #Calculating Right Node
        minE=index

        """ Calculating the Minimum element Value from the List """
        if left <= size and self.heap[left] < self.heap[index]:
            minE=left

        if right <= size and self.heap[right] < self.heap[minE]:
            minE=right

        if minE != index:  # Swapping elelments only when MinE is not equal to the Parent Node
            self.swap(minE, index)
            self.heapify(minE)

    """ Method to Swap the elements of the Heap List  """

    def swap(self,first, second):
        self.heap[first],self.heap[second] = self.heap[second], self.heap[first]


    def minHeap(self): # Main calling Method to perform Heap

        loc=len(self.heap)-1 

        i=0
        while i <= loc:  #Running the Loop till the last element
            self.heapify(i)
            i+=1

heapList=Heap()

heapList.insert(10)
heapList.insert(15)

heapList.insert(5)
heapList.insert(2)
heapList.insert(18)
heapList.insert(3)

print(" Original List")
heapList.printHeap()

print(" Performing Heap sort:")
heapList.minHeap()

print("Final Result: ")
heapList.printHeap()

Результат, который я получаю из приведенного выше кода: 

Original List
[10, 15, 5, 2, 18, 3]
 Performing Heap sort:
****Final Result:
[5, 2, 3, 15, 18, 10]

Однако ожидается, что будет: 

[2,5,3,15,18,10]

Буду признателен за ваши ценные комментарии. Спасибо!

...