我试图通过传递一个整数数组来构建一个二进制堆。我想知道是否应该先构建一个 BinaryTree 类,然后再构建一个 Heap 类以实现二进制堆,还是应该构建一个二进制堆类?我很困惑..谢谢!
4 回答
二叉堆是一种特殊的二叉树。应该维护堆属性。
来自 Wikipedia 的复习:如果 A 是 B 的父节点,则节点 A 的键相对于节点 B 的键进行排序,并且在堆中应用相同的排序。要么父节点的key总是大于等于子节点的key,最高的key在根节点(这种堆称为max heap),要么父节点的key小于等于子节点的key子节点和最低键位于根节点(最小堆)中。
根据您的实现,还有一些关于堆完整性的规则。
二叉树不一定具有二叉搜索树属性。
因此,换句话说,只需将二叉堆实现为具有所讨论的特殊功能的树。
可以简单地使用数组来表示和存储二叉堆。无需先构建/实现二叉树。
请查看以下有关如何将二进制堆表示为数组的链接:http ://www.cse.hut.fi/en/research/SVG/TRAKLA2/tutorials/heap_tutorial/taulukkona.html
确保理解 Parent(i)、Left(i) 和 Right(i) 的概念。另外,看看 build-heap 函数从一个未排序的数组构建一个堆:http ://en.wikipedia.org/wiki/Binary_heap#Building_a_heap
您从树中的第一个非叶节点开始,一直调用heapify
直到根。
这是 python 中的一个示例,它在数组中构建二进制堆。
def add_data(heap, data):
for i in range(0, len(data)):
item = data[i]
insert(heap, item)
if not is_heap_ordered(heap):
raise Exception("explode!")
def insert(heap, x):
heap.append(x)
swim(heap, len(heap) - 1)
def swim(heap, k):
parent = k / 2
while (k > 1) and (heap[parent] < heap[k]):
exchange(heap, k, parent)
k = parent
parent = k / 2
def is_heap_ordered(heap):
# heap property: parent is >= children
limit = len(heap)
for k in range(1, limit):
if ((2 * k) > limit - 1) or (((2 * k) + 1) > limit - 1):
break
node = heap[k]
parent = heap[k / 2]
if k / 2 < 1: # root node
parent = node
childl = heap[2 * k]
childr = heap[(2 * k) + 1]
if childl > parent or childr > parent:
print "heap violated"
return False
return True
def exchange(array, i, j):
temp = array[i]
array[i] = array[j]
array[j] = temp
heap = []
input = list("ABCDEF")
random.shuffle(input)
add_data(heap, input)
不使用数组的第一个元素,这使得数学更简单一些。
每个节点在位置 k 的子节点位于 2k 和 2k+1 每个节点的父节点在位置 k/2
该算法是:将一个元素附加到数组的末尾,然后为该元素调用游泳,直到它处于正确的堆位置(堆服从“堆属性”)。堆属性是每个父级 >= 其子级。
这是算法工作的动画
#Binary Heap with all the common operations
"""This Code will generate Min Binary Heap with all action that we can perform on Binary Heap. The Formula i have taken is in array 0'th position will be None, Will start from 1'st Position. So root will be at 1 ant left will be at 2x(2) right will be 2x+1(3) Position. """
class MinHeap():
""" Min Heap:-Node values will always be lees than the left and right child """
def __init__(self):
#Creating a Array to push heap values
self.heap_list=[None]
def push_element(self,value):
self.heap_list.append(value)
#Getting right child from postion 2x
def get_left_child(self,index):
for i in range(len(self.heap_list)):
if i==2*index:
return self.heap_list[2*index]
return 999
#Getting right child from postion 2x+1
def get_right_child(self,index):
for i in range(len(self.heap_list)):
if i==2*index+1:
return self.heap_list[2*index+1]
return 999
# I have considered a logic node if node will on x index then left child woul bw at 2*x and right child will be at 2*x+1 postion in array
def re_construct_heap(self):
for i in range(1,(len(self.heap_list)//2)+1):
left_child=self.get_left_child(i)
right_child=self.get_right_child(i)
if self.heap_list[i]>left_child :
v_parent=self.heap_list[i]
self.heap_list[i]=left_child
self.heap_list[2*i]=v_parent
elif self.heap_list[i]>right_child:
v_parent=self.heap_list[i]
self.heap_list[i]=right_child
self.heap_list[2*i+1]=v_parent
#Re cunstructing heap till the heap property satisfies
def build_min_heap(self):
for i in range(len(self.heap_list)//2, 0, -1):
self.re_construct_heap()
#Deleing a root node and trying to rebuild Min Heap with heap property
def delte_node_heap(self,value):
if self.heap_list[1]==value:
self.heap_list[1]=self.heap_list[-1]
self.heap_list.pop(-1)
self.build_min_heap()
#Min Value of Heap
def min_value(self):
return self.heap_list[1]
#Max Value of Heap
def max_value(self):
return self.heap_list[-1]
#size of heap
def size_of_heap(self):
return len(self.heap_list)
#Printin Heap Values
def print_min_heap(self):
for i in self.heap_list:
print(i,end='->')
min_heap_obj=MinHeap()
min_heap_obj.push_element(3)
min_heap_obj.push_element(5)
min_heap_obj.push_element(8)
min_heap_obj.push_element(17)
min_heap_obj.push_element(19)
min_heap_obj.push_element(36)
min_heap_obj.push_element(40)
min_heap_obj.push_element(25)
min_heap_obj.push_element(100)
#insert a node less than root node
#min_heap_obj.push_element(1)
#re structuring heap with heap property
min_heap_obj.build_min_heap()
#deleting a root node
min_heap_obj.delte_node_heap(3)
#re structuring heap with heap property
min_heap_obj.build_min_heap()
#printing heap values
min_heap_obj.print_min_heap()
print('\n')
print(min_heap_obj.min_value(),min_heap_obj.max_value(),min_heap_obj.size_of_heap())