5
\$\begingroup\$

I'm trying to Implement a d-ary heap. A d-ary heap is just like a regular heap but instead of two childrens to each element, there are d childrens! d is given when building a heap, either by giving an argument or by passing it while calling init.

Here is my Implementation:

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)

So, this is my implementation, I hope it's fine. Also, I'd like to have some review for my code.

  1. Time complexity is fine?
  2. Any chances for the code to fail or raise an Error that I missed?

Also, here are my tests until now (not finished), I don't know how to check for other d's because I have to check all of them by hand and then make the tests.. if you have any recommendations I'll be happy to hear! :

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()

Thanks!

\$\endgroup\$
  • 1
    \$\begingroup\$ Hi, it would be much appreciated if you could describe what is the d-ary heap here without having to link to Wikipedia. I assure you you'll have more attention to your post if you do this. \$\endgroup\$ – IEatBagels Aug 12 at 15:28
  • 1
    \$\begingroup\$ @IEatBagels Added an explanation! \$\endgroup\$ – Matan Cohen Aug 12 at 15:34
2
\$\begingroup\$

Nice implementation. Don't be alarmed by this list of thoughts/opinions/observations:

In __init__, it might make more sense to make both parameters optional with default values. You wouldn't normally expect a library to interactively ask for missing parameters.

Python code typically isn't written to check types at runtime.

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

    self.heap = heap or list()

    self.d = d

    self.build_d_heap()

It isn't necessary to keep track of the length of the heap. Just use len(self.heap). It is already O(1).

Starting a class member name starting with '_' tells users that it is not part of the public interface of the class and it might change. So it might be good to use _child(), _parent(), etc. because these are internal implementation specific methods.

A '__' (without a trailing '__') tells the python compiler to mangle the class member name. This is mostly to prevent name collisions when a class is intended for subclassing.

It is not common in Python code to provide setters or getters and the like. Just let the user access the class member directly. If the implementation needs to be changed, a property can be used to avoid changing the interface.

Defining a __len__() method implements the builtin len() function for your container class.

Triple quoted strings can have multiple lines, so you don't need to use them at the beginning and end of every line. Docstrings typically go inside a function/method definition not before it.

According to the wikipedia article, the index of the parent is math.floor(i/self.d)-1. It also says to heapify an list, start at the end of the list not at (length-1)//d.

dheap_increase_key() doesn't seem to be used anywhere.

dheap_insert() looks like heap items can only be int, which would be extremely limiting. To be more useful, a heap item should be anything that can be compared (<), such as strings, tuples, lists, classes with __lt__() method, etc.

That's all for now.

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

can be simplified to:

    self.__heap[0] = self.__heap.pop()
\$\endgroup\$
  • \$\begingroup\$ Thank you so much! Actually most of the things you mentioned are known but the limitations I had in this project made me took those paths! Much appreciate! Also, do you know maybe how can I test my class without writing a lot of code? \$\endgroup\$ – Matan Cohen Aug 13 at 11:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.