gpt4 book ai didi

python - Python中堆数据结构如何实现max heapify

转载 作者:太空宇宙 更新时间:2023-11-04 04:40:13 27 4
gpt4 key购买 nike

下面是堆类。我正在尝试对堆进行排序,但我的 max_heapify 函数有问题。我插入了值 [10, 9, 7, 6, 5, 4, 3] 并且我的堆排序打印给定的输出。给定的输出和期望的输出在类下面给出

堆的类别

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

def insert(self, x):
self.A.append(x)

def Max(self):
"""
returns the largest value in an array
"""
return max(self.A)

def extractMax(self):
"""
returns and remove the largest value from an array
"""
x = max(self.A)
self.A.remove(x)
self.max_heapify(0)
return x;

def parent(self, i):
"""
returns the parent index
"""
i+=1
i = int(i/2)
return i

def left(self, i):
"""
returns the index of left child
"""
i = i+1
i = 2*i
return i

def right(self, i):
"""
returns the index of right child
"""
i+=1;
i = 2*i + 1
return i

def heap_size(self):
"""
returns the size of heap
"""

return len(self.A)

def max_heapify(self, i):
"""
heapify the array
"""
l = self.left(i)
r = self.right(i)

if(l < self.heap_size() and self.A[l] > self.A[i]):
largest = l
else:
largest = i

if(r < self.heap_size() and self.A[r] > self.A[largest]):
largest = r


if largest != i:

temp = self.A[i]
self.A[i] = self.A[largest]
self.A[largest] = temp

self.max_heapify(largest)


def build_max_heap(self):

n = len(self.A)
n = int(n/2)
for i in range(n, -1, -1):
self.max_heapify(i)


def heap_sort(self):
"""
sorts the heap
"""

while self.heap_size() > 0:

self.build_max_heap()
temp = self.A[0]
n = len(self.A) - 1
self.A[0] = self.A[n]
self.A[n] = temp
x = self.A.pop()
print(x)
self.max_heapify(0)




h = Heap()
h.insert(10)
h.insert(9)
h.insert(7)
h.insert(6)
h.insert(5)
h.insert(4)
h.insert(3)
h.heap_sort()

给定输出

10
7
6
5
4
3
9

预期输出

10
9
7
6
5
4
3

最佳答案

看起来您正在尝试构建一个根位于 A[0] 的最大堆。如果那是正确的,那么您的 leftrightparent 索引计算不正确。你有:

def parent(self, i):
"""
returns the parent index
"""
i+=1
i = int(i/2)
return i

def left(self, i):
"""
returns the index of left child
"""
i = i+1
i = 2*i
return i

def right(self, i):
"""
returns the index of right child
"""
i+=1;
i = 2*i + 1
return i

因此,如果 i=0,则左 child 为 2,右 child 为 3。更糟糕的是,给定 i=3parent 将返回 2。所以你遇到了 parent(right(i)) != i 的情况。这永远行不通。

正确的计算是:

left = (2*i)+1
right = (2*i)+2
parent = (i-1)/2

我不知道为什么你的 extractMax 调用 max(self.A)。您已经知道最大元素位于 A[0]。要提取最大项,您需要做的就是:

returnValue = save value at self.A[0]
take last item in the array and place at self.A[0]
decrease length of array
maxHeapify(0)

我使用伪代码是因为我对 Python 不是特别满意。

heapSort 方法中的循环严重不理想。您在每次迭代时调用 self.build_max_heap。你不需要那样做。如果 extractMax 工作正常,您只需:

while self.heap_size() > 0:
temp = self.extractMax()
print temp

现在,如果您想就地对数组进行排序,以便对 self.A 本身进行排序,那就有点棘手了。但看起来这并不是您想要做的。

关于python - Python中堆数据结构如何实现max heapify,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/50829546/

27 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com