Calculate Sum Of Leaf Nodes In A Heap

A binary heap is a heap data structure that takes a form of binary tree. Heaps are commonly implemented using array.

A heap is classified into two types which are min or max heap. In min heap the parent node is less than its children. While in max heap parent node is greater than its children.

The insertion is left to right and maintains the heap property for min or max heap. So an insertion results in an additional operation where the property of min or max heap is maintained by swap nodes.

Similarly deletion also maintains the heap property by swapping parent and children nodes.

Problem

The problem here is to calculate the sum of leaf nodes in a heap. The input is min heap to the function sum_heap_leaf_nodes which calculate the sum of leaf nodes.


[(1,2), (1,3), (2,4), (2,5), (3, 6), (3, 8)]

The input is an array of tuples. So here we already have a min heap. Some might construct a heap using the data, but my take is that heap is a binary so we can count the leap parent nodes from the end of the tree up-to 2 parent nodes. In the above input it will parent node 2, and node 3. In addition it is possible that the tree is not balanced so we don’t want to count the parent nodes which have children’s like the following example.

In the above min tree there are two parent nodes 4 and 5. So the last two nodes are 4 and 5. So an additional check is needed not to count the node 5 as it a child of parent node 1.

import sys
def sum_heap_leaf_nodes(hp):
    #create a dictionary of the parents
    mydict = {}
    child = []
    for tup in hp:
        # create array first time for parents children's
        if tup[0] not in mydict:
            mydict[tup[0]] = []
        mydict[tup[0]].append(tup[1])
    # need to iterate the dictionary in reverse to calculating the size
    size = len(mydict)
    tot = 0;
    for key in mydict:
        # if the size of the size of traversed dictionary is less than 3 we are on the
        # the last 2 parent nodes.
        if (size < 3):
           for val in mydict[key]:
                if val not in mydict:
                    tot = tot + val
        size = size - 1
    print (mydict)
    return tot
def main():
   tot = sum_heap_leaf_nodes([(1,2), (1,3), (2,4), (2,5), (3, 6), (3, 8)])
   assert tot == 23 # tot equal 23
   tot = sum_heap_leaf_nodes([(4,1), (4,5), (5,3), (5,6)])
   assert tot == 10 # tot equal 10
if __name__ == '__main__':
    sys.exit(main())