实现d元堆

Question

我正在尝试实现一个d-ary堆。d-ary堆就像一个常规堆，但是不是每个元素有两个子元素，而是有d子元素！在构建堆时，通过提供参数或在调用init时传递它，就会给出d。

以下是我的实现：

import math

class DHeap:
    ''' creates d-heap '''
    ''' heap: A python's list '''

    def __init__(self, heap: list, d: int=None):
        if type(heap) is list:
            self.__heap = heap
        else:
            raise TypeError("Argument heap is not a list!")
        if not d:
            try:
                self.__d = int(input('Please insert d: '))
            except ValueError:
                print("Not a valid integer")
        else:
            self.__d = d
        self.__length = len(heap)
        self.build_d_heap(self.d)

    @property
    def d(self):
        return self.__d

    @d.setter
    def d(self, d):
        if self is None:
            self.__d = d
        else:
            pass

    @property
    def length(self):
        return len(self.__heap)

    @length.setter
    def length(self, new_len):
        self.__length = new_len

    def build_d_heap(self, d):
        ''' i is exactly as the regular binary heap '''
        ''' this time instaed of using LENGTH/2 I used LENGHT/d '''
        ''' // is floor division in Python '''
        i = (self.length-1)//d
        for i in range(i, -1, -1):  # O(n/d)
            self.dheap_max_heapify(i)

    def __str__(self):
        return str(self.__heap)

    ''' return the kth child of index i '''
    ''' k >= 0 and k <= d-1 '''
    ''' Constant time Complexity '''
    def child(self, k: int, i: int) -> int:
        return self.d*i+1+k

    def parent(self, i: int) -> int:
        return math.ceil(i/self.d)-1

    """ The implementation of dheap_max_heapify is pretty
        similar to the original heapify implementation.
        the main changes are the choosing of the largest number of each
        "subtree" in order to make changes!
        The Time Complexity of this heapify is: O(d log d (n)). """
    def dheap_max_heapify(self, i: int):
        largest = i  # O(1)
        for k in range(0, self.d):  # O(d)
            # O(1)
            if self.child(k, i) < self.length and self.__heap[self.child(k, i)] > self.__heap[i]:
                if self.__heap[self.child(k, i)] > self.__heap[largest]:  # O(1)
                    largest = self.child(k, i)  # O(1)

        if largest != i:  # O(1)
            # O(1) - swapping
            self.__heap[i], self.__heap[largest] = self.__heap[largest], self.__heap[i]
            ''' This recursive call is happening at most Tree-Height times '''
            self.dheap_max_heapify(largest)

    """ The implementation of d-ary heap_extract max as shown,
        in order to make the implementation work I had to implement
        the d-ary max_heapify.
        My implementation for dheap_extract_max is using constant time
        operations alongside the dheap_max_heapify method which the time
        complexity of this method is described just before implementation.
        TOTAL TIME: O(d log d (n)). """
    def dheap_extract_max(self):
        if self.length < 1:
            raise AttributeError("Heap is Empty")
        rv = self.__heap[0]
        self.__heap[0] = self.__heap[self.length-1]
        self.__heap.pop()
        self.dheap_max_heapify(0)
        return rv

    def dheap_insert(self, key: int):
        ''' check if key is valid '''
        if type(key) is int:  # O(1)
            self.__heap.append(key)  # O(1) - adding key to the end of heap.
            i = self.length-1  # O(1)
            self.dheap_upwords_heapify(i)  # fixing the heap.

    def dheap_increase_key(self, i: int, key: int):
        ''' check for error chances '''
        if i < 0 or i >= self.length:
            raise IndexError("Index out of range")
        if type(key) is not int or key < self.__heap[i]:
            raise ValueError("Error, Invalid key")
        self.__heap[i] = key  # set heap[i] as new key
        ''' call method to fix heap '''
        self.dheap_upwords_heapify(i)

    """ dheap_upwords_heapify created in order to keep my code clean.
        While creating insert and increase-key I had to use the same
        methods in order to "fix" the d-ary heap and in order not to
        duplicate my code I made a new method.
        This method takes i (index) and fixing the d-ary heap
        from this i and upwords (unlike heapify who goes downwords).
        Time complexity: O(log d (n)) bounded by the tree-height. """
    def dheap_upwords_heapify(self, i: int):
        # O(log d (n))
        while i > 0 and self.__heap[self.parent(i)] < self.__heap[i]:
            self.__heap[i], self.__heap[self.parent(i)] = self.__heap[self.parent(i)], self.__heap[i]
            i = self.parent(i)

所以，这是我的实现，我希望它是好的。另外，我还想对我的代码进行一些回顾。

1. 时间复杂度可以吗？
2. 代码是否有可能失败或引发我错过的错误？

另外，这是我的测试，直到现在(还没有完成)，我不知道如何检查其他的d，因为我必须检查所有的手，然后进行测试。如果你有任何建议，我会很高兴听到！

from dheap import DHeap

# TESTS


def main():

    ''' LIST CREATION '''

    # All test cases are trinary heap (3 ary heap)
    # Each case is a tuple with input and expected output
    # None
    none = (None, None)
    # Empty
    empty = ([], [])
    # Full
    full = ([1, 2, 3, 4, 5, 6], [6, 5, 3, 4, 1, 2])
    # Full with negative and equal numbers
    negatives_and_equals = ([-4, 2, -3, -10, 20, 32, -4],
                            [32, 20, -3, -10, -4, 2, -4])
    # Full with wrong types
    full_with_wrong_types = ([1, 3, 22, 'a', 'WRONG', []], None)
    # List of those cases
    test_cases = [none, empty, full,
                  full_with_wrong_types, negatives_and_equals]

    output = []  # Output list for heaps and next tests
    # Iterate over the list and check each case
    for i in range(len(test_cases)):
        print(f'------------- Creation test number: {i+1} -------------')
        # `test_cases[i][0]` is the input
        print(f'Testing heap construction as {test_cases[i][0]}')
        try:
            # Call __init__ with d=3
            heap = DHeap(test_cases[i][0], 3)
            print('Heap created succesffuly')
            # `test_cases[i][0]` is the expected output
            print(f'Excpected:\t {test_cases[i][1]}')
            # Printing heap as an array (python's list)
            print(f'Resault:\t {heap}')
            output.append(heap)
        # check for TypeError (Creation)
        except TypeError:
            print('Given arguemtns are wrong!')

    # Extract max test for each heap
    print('\nCheck heap extract max for each heap\n')
    expect = [None, 6, 32]
    for i in range(len(output)):
        output[i] = (output[i], expect[i])
    i = 1
    for h, m in output:
        print(f'------------- Extract max test number {i} -------------')
        try:
            print(f'Expected max:\t {m}')
            print(f'Real max:\t {h.dheap_extract_max()}')
        except AttributeError:
            print('Empty list:\t None')
        i += 1

    # Check if heap is fine
    print('\nCheck if heap is fine after extraction of max\n')
    expect = [[], [5, 2, 3, 4, 1], [20, 2, -3, -10, -4, -4]]
    for i in range(3):
        output[i] = (output[i][0], expect[i])
    for counter, h in enumerate(output):
        print(f'------------- Test heap number {counter+1} -------------')
        print(f'Expected heap:\t {h[1]}')
        print(f'Current heap:\t {h[0]}')

    # Reset output to lists only
    for i in range(len(output)):
        output[i] = output[i][0]

    print('\nInsert test\n')
    # Insert negative
    for h in output:
        h.dheap_insert(-8)

    expect = [[-8], [5, 2, 3, 4, 1, -8], [20, 2, -3, -10, -4, -4, -8]]
    for i in range(len(output)):
        print(f'Insertion test number {i+1}')
        print(f'Expected:\t {expect[i]}')
        print(f'Current:\t {output[i]}')

    # Insert Big
    # Insert equals
    # Insert small (deprected)
    # Insert non-int


if __name__ == '__main__':
    main()

谢谢!

Answer 1

很好的实现。不要对这一系列的想法/意见/观察感到惊慌：

在__init__中，使用默认值使这两个参数都是可选的可能更有意义。通常，您不会期望库以交互方式请求缺少参数。

Python代码通常不是用来在运行时检查类型的。

def __init__(self, heap: list=None, d: int=1):

    self.heap = heap or list()

    self.d = d

    self.build_d_heap()

没有必要跟踪堆的长度。只需使用len(self.heap)。它已经是O(1)了。

从'_'开始的类成员名告诉用户，它不是类的公共接口的一部分，它可能会改变。因此，使用_child()、_parent()等可能更好，因为这些是内部实现的特定方法。

一个'__' (没有尾随的'__')告诉python编译器损坏类成员的名称。这主要是为了防止类用于子类时的名称冲突。

在Python代码中，提供setter或getter之类的东西并不常见。只需让用户直接访问类成员即可。如果需要更改实现，则可以使用属性来避免更改接口。

定义__len__()方法实现容器类的内置len()函数。

三重引号字符串可以有多行，所以不需要在每一行的开头和结尾使用它们。Docstring通常在函数/方法定义中，而不是在它之前。

根据维基百科的文章，父类的索引是math.floor(i/sel.d)-1。它还说，为了使一个列表更好，从列表的末尾开始，而不是(长度-1)//d。

dheap_increase_key()似乎不在任何地方使用。

dheap_insert()看起来像堆项只能是int，这将是非常有限的。为了更有用，堆项应该是任何可以比较的东西(<)，例如字符串、元组、列表、使用__lt__()方法的类等等。

这就是目前的情况。

    self.__heap[0] = self.__heap[self.length-1]
    self.__heap.pop()

可简化为：

    self.__heap[0] = self.__heap.pop()