-1

我试图通过传递一个整数数组来构建一个二进制堆。我想知道是否应该先构建一个 BinaryTree 类,然后再构建一个 Heap 类以实现二进制堆,还是应该构建一个二进制堆类?我很困惑..谢谢!

4

4 回答 4

1

二叉堆是一种特殊的二叉树。应该维护堆属性。

来自 Wikipedia 的复习:如果 A 是 B 的父节点,则节点 A 的键相对于节点 B 的键进行排序,并且在堆中应用相同的排序。要么父节点的key总是大于等于子节点的key,最高的key在根节点(这种堆称为max heap),要么父节点的key小于等于子节点的key子节点和最低键位于根节点(最小堆)中。

根据您的实现,还有一些关于堆完整性的规则。

二叉树不一定具有二叉搜索树属性。

因此,换句话说,只需将二叉堆实现为具有所讨论的特殊功能的树。

于 2014-02-18T19:48:38.610 回答
0

可以简单地使用数组来表示和存储二叉堆。无需先构建/实现二叉树。

请查看以下有关如何将二进制堆表示为数组的链接: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直到根。

于 2014-02-18T19:48:00.053 回答
0

这是 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

该算法是:将一个元素附加到数组的末尾,然后为该元素调用游泳,直到它处于正确的堆位置(堆服从“堆属性”)。堆属性是每个父级 >= 其子级。

这是算法工作的动画

在此处输入图像描述

于 2017-03-28T19:08:08.450 回答
0
#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())
于 2020-10-02T06:58:46.713 回答