python - 如何在 Python 的堆数据结构中实现 max_heapify
问题描述
下面是一个堆类。我正在尝试对堆进行排序,但我的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]
. 如果这是正确的,那么您的left
,right
和parent
index 计算不正确。你有:
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
,左孩子将是 2,而右孩子将是 3。更糟糕的是,给定i=3
,parent
将返回 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
对其本身进行排序,那就有点棘手了。但看起来这不是你想要做的。
推荐阅读
- java - JSON 模式验证对 PropertyName 没有按预期工作
- python - 如何使用networkx检索没有目标节点的源节点的所有路径
- redux - 无法读取未定义的属性“绑定”
- sql-server - 为什么 django 中的 indpectdb 没有创建所有表模型?
- ruby - 如何拆分字符并保持价值
- javascript - 如何从服务器加载 SVG 并将它们内联插入
- jscript - 导致警报的标头脚本
- android - Ubuntu 18.04 React Native 运行 Android javax.net.ssl.SSLException
- sql-server - SQL 是 LEFT JOIN 和 WHERE 语句的最佳替代方案?
- ios - 将 UIScrollView 中的内容视图固定到其底部而不是其顶部边缘