创建最大-最小优先级队列时遇到问题(python)[已关闭]

- 已关闭**。此问题需要超过focused。当前不接受答案。
- 想要改进此问题吗？**更新此问题，使其仅关注editing this post的一个问题。

56分钟前就关门了。
Improve this question
我在python中做了一个最小最大优先级队列，我用我的例子测试了它，没有问题，但是编码网站（像leetcode这样的网站）说输出是错误的（不是错误）......有什么问题/改进我可以做的吗？
我认为有一个进口，我可以使这一部分更容易（我认为），但我试图得到正确的概念之前，进口它在未来。

class MaxMinHeap:
    def __init__(self, max_len):
        self.heap_arr = [0 for _ in range(max_len + 1)]
        self.arr_len = 0

    # checks if heap is empty
    def empty(self):
        if self.arr_len == 0:
            return True
        return False

    # checks if the level of the tree is an odd number or an even number
    def is_min_level(self):
        if math.floor(math.log2(self.arr_len)) % 2 == 1:
            return False
        return True

    # inserts a number to the heap
    def insert_num(self, input_num):
        self.arr_len += 1
        self.heap_arr[self.arr_len] = input_num
        # if the array was empty, don't do any checks
        if self.arr_len == 1:
            return
        # else if the array is at the min level of the tree
        elif self.is_min_level():
            self.min_insert()
        else:
            self.max_insert()

    # when a number is added to the heap at the max level
    def max_insert(self):
        # if the child is bigger than the number
        if self.heap_arr[self.arr_len // 2] > self.heap_arr[self.arr_len]:
            # change the values
            self.heap_arr[self.arr_len], self.heap_arr[self.arr_len // 2] = self.heap_arr[self.arr_len // 2], self.heap_arr[self.arr_len]
            # keep updating the values up the min tree
            self.minify_up(self.arr_len // 2)
        else:
            # keep updating the values up the max tree
            self.maxity_up(self.arr_len)

    # when a number is added to the heap at the min level
    def min_insert(self):
        # if the child is smaller than the number
        if self.heap_arr[self.arr_len // 2] < self.heap_arr[self.arr_len]:
            # change the values
            self.heap_arr[self.arr_len], self.heap_arr[self.arr_len // 2] = self.heap_arr[self.arr_len // 2], self.heap_arr[self.arr_len]
            # keep updating the values up the max tree
            self.maxity_up(self.arr_len // 2)
        else:
            # keep updating the values up the min tree
            self.minify_up(self.arr_len)

    # when a max number is needed
    def max_output(self):
        if self.empty():
            return -1
        # if there is only one number(the first node is in the min level) return that node
        if self.arr_len == 1:
            self.arr_len -= 1
            return self.heap_arr[1]
        # else check the second and third node to get max num
        temp_index = 2
        if temp_index + 1 <= self.arr_len and self.heap_arr[temp_index] < self.heap_arr[temp_index + 1]:
            temp_index += 1
        # change with the last element
        self.heap_arr[self.arr_len], self.heap_arr[temp_index] = self.heap_arr[temp_index], self.heap_arr[self.arr_len]
        self.arr_len -= 1
        # go updating down the array
        self.maxify_down(temp_index)
        # print the max that was changed with the last element
        return self.heap_arr[self.arr_len + 1]

    # when a min number is needed
    def min_output(self):
        if self.empty():
            return -1
        # change with the last element(the min number is always at index 1)
        self.heap_arr[self.arr_len], self.heap_arr[1] = self.heap_arr[1], self.heap_arr[self.arr_len]
        self.arr_len -= 1
        # go updating down the array
        self.minify_down(1)
        # print the min that was changed with the last element
        return self.heap_arr[self.arr_len + 1]

    # when an output is sent from the max level
    def maxify_down(self, input_index):
        # while the node has a child
        while input_index * 2 <= self.arr_len:
            # if there are no grandchild
            if input_index * 4 > self.arr_len:
                # check the child
                comp_index = input_index * 2
                if comp_index + 1 == self.arr_len and self.heap_arr[comp_index] < self.heap_arr[comp_index]:
                    comp_index += 1
                # if any of the child are bigger change values
                if self.heap_arr[input_index] < self.heap_arr[comp_index]:
                    self.heap_arr[input_index], self.heap_arr[comp_index] = self.heap_arr[comp_index], self.heap_arr[input_index]
                # end update
                return
            # else set the comparing element to its right child
            # this is because the right child might have no child. Making this node have no guarantee that it is
            # smaller than the grandchild
            comp_index = input_index * 2 + 1
            # loop through the grandchild list
            for temp_index in range(input_index * 4, input_index * 4 + 4):
                if temp_index + 1 == self.arr_len and self.heap_arr[comp_index] < self.heap_arr[temp_index]:
                    comp_index = temp_index
            # swap the max number with the index
            self.heap_arr[input_index], self.heap_arr[comp_index] = self.heap_arr[comp_index], self.heap_arr[input_index]
            # if the swaped index was the child one end update
            if comp_index == input_index * 2 + 1:
                return
            # else check the parent of the node for any errors
            if self.heap_arr[comp_index] < self.heap_arr[comp_index // 2]:
                self.heap_arr[comp_index // 2], self.heap_arr[comp_index] = self.heap_arr[comp_index], self.heap_arr[comp_index // 2]
            # set the index again and loop
            input_index = comp_index

    # when an output is sent from the max level
    def minify_down(self, input_index):
        # while the node has a child
        while input_index * 2 <= self.arr_len:
            # if there are no grandchild
            if input_index * 4 > self.arr_len:
                # check the child
                comp_index = input_index * 2
                if comp_index + 1 == self.arr_len and self.heap_arr[comp_index] > self.heap_arr[comp_index]:
                    comp_index += 1
                # if any of the parents are bigger change values
                if self.heap_arr[input_index] > self.heap_arr[comp_index]:
                    self.heap_arr[input_index], self.heap_arr[comp_index] = self.heap_arr[comp_index], self.heap_arr[input_index]
                # end update
                return
            # else set the comparing element to its right child
            # this is because the right child might have no child. Making this node have no guarantee that it is
            # bigger than the grandchild
            comp_index = input_index * 2 + 1
            # loop through the grandchild list
            for temp_index in range(input_index * 4, input_index * 4 + 4):
                if temp_index + 1 == self.arr_len and self.heap_arr[comp_index] > self.heap_arr[temp_index]:
                    comp_index = temp_index
            # swap the min number with the index
            self.heap_arr[input_index], self.heap_arr[comp_index] = self.heap_arr[comp_index], self.heap_arr[input_index]
            # if the swaped index was the child one end update
            if comp_index == input_index * 2 + 1:
                return
            # else check the parent of the node for any errors
            if self.heap_arr[comp_index] > self.heap_arr[comp_index // 2]:
                self.heap_arr[comp_index // 2], self.heap_arr[comp_index] = self.heap_arr[comp_index], self.heap_arr[comp_index // 2]
            # set the index again and loop
            input_index = comp_index

    # when input is in max level
    def maxity_up(self, input_index):
        # while the input has a grandfather
        while input_index // 4 > 0:
            # compare grandfather with input and if input is greater swap
            comp_index = input_index // 4
            if self.heap_arr[comp_index] >= self.heap_arr[input_index]:
                break
            self.heap_arr[comp_index], self.heap_arr[input_index] = self.heap_arr[input_index], self.heap_arr[comp_index]
            # update index and loop
            input_index = comp_index

    # when input is in min level
    def minify_up(self, input_index):
        # while the input has a grandfather
        while input_index // 4 > 0:
            # compare grandfather with input and if input is smaller swap
            comp_index = input_index // 4
            if self.heap_arr[comp_index] <= self.heap_arr[input_index]:
                break
            self.heap_arr[comp_index], self.heap_arr[input_index] = self.heap_arr[input_index], self.heap_arr[comp_index]
            # update index and loop
            input_index = comp_index

用于存储的数组是heap_arr，堆从索引1开始，使子级和父级分别为//2和 * 2。
我试着去查一份研究论文，并试着把它的伪代码复制到python上，但得到了同样的结果。为我的例子工作，但不是为网站。

你的minify_down（和maxity_down）方法有bug，事实上，你可以很容易地发现这个问题，因为只有四个值就已经出错了。
我将首先展示一些您可以自己调试的步骤：
1.定义一个方法，在人类可读的"树视图"中打印堆。只是一个90 °（逆时针）旋转的视图，其中根显示在左侧，树延伸到右侧：

def print(self, i=1, tab=""):
    if i > self.arr_len:
        return
    self.print(i*2 + 1, tab+"  ")
    print(tab, self.heap_arr[i])
    self.print(i*2, tab+"  ")

1.定义一个验证堆一致性的方法，如果不一致，则打印堆并抛出错误：

def verify(self, i=1, ismin=True, low=-100000, high=100000):
    if i > self.arr_len:
        return
    val = self.heap_arr[i]
    if not(low <= val <= high):
        self.print()
        raise ValueError(f"inconsistent heap at {val}")
    if ismin:
        low = val
    else:
        high = val
    self.verify(i*2, not ismin, low, high)
    self.verify(i*2+1, not ismin, low, high)

1.创建一些随机输入并将这些值提供给堆，在每次调用insert之后，还要调用上面的verify方法。

import random

orig = list(range(20))
for i in range(100):  # repeat a few times with different shuffles of input
    values = orig[:]
    random.shuffle(values)
    heap  = MaxMinHeap(len(values)+3)  # Allocate enough space for the heap
    for value in values:  # Insert the values in their shuffled order
        heap.insert_num(value)
        heap.verify()  # ... and each time verify all is well

1.如果上述测试结果良好（确实如此），则继续在测试中添加min_output调用

import random

orig = list(range(20))
for i in range(100):  # repeat a few times with different shuffles of input
    values = orig[:]
    random.shuffle(values)
    heap  = MaxMinHeap(len(values)+3)  # Allocate enough space for the heap
    for value in values:  # Insert the values in their shuffled order
        heap.insert_num(value)
        heap.verify()  # ... and each time verify all is well

    res = []  # output of values as they are removed from the heap
    while not heap.empty():
        res.append(heap.min_output())
        heap.verify()

    if res != orig:
        print(values)
        print("Removal was not in order", res)
        break

此测试失败!将orig列表的大小减少到甚至只有4个值时，出现了类似[3，1，0，2]的混洗values错误。这是一个很好的候选项，可以进一步深入到导致不一致的原因（请参阅进一步内容）。
1.您可以以相同的方式继续max_output测试。
1.一旦您发现哪个状态导致堆不一致，就可以开始调试，调试器会逐步调试代码、检查名称等等
我只能敦促不要这么快就放弃一个问题：设计像上面这样的测试实际上并不困难，它帮助你在合理的时间内识别问题。

结论

我在minify_down中发现了这些问题：
1.在一些地方你有if .... == self.arr_len，它排除了测试索引实际上 * 小于 * 那个限制的情况，而那些索引也应该被允许通过那个测试，所以改为<=。
1.有一个self.heap_arr[comp_index] > self.heap_arr[comp_index]测试，显然没有意义。
1.条件temp_index + 1 == self.arr_len不仅应该更正为使用<=（第1点），而且应该是temp_index <= self.arr_len，因为您的目的是访问self.heap_arr[temp_index]，而不是self.heap_arr[temp_index+1]
1.再往下，您执行交换 * 而不检查是否需要此交换 *!因此请更改此设置：

self.heap_arr[input_index], self.heap_arr[comp_index] = self.heap_arr[comp_index], self.heap_arr[input_index]

致：

if self.heap_arr[input_index] > self.heap_arr[comp_index]:
    self.heap_arr[input_index], self.heap_arr[comp_index] = self.heap_arr[comp_index], self.heap_arr[input_index]

有了这些更改，上面的测试代码将通过。类似的问题存在于maxify_down中，您可以沿着相同的路线更正。

创建最大-最小优先级队列时遇到问题(python)[已关闭]

1条答案

结论

相关问题

热门标签

最新问答