Heap

A heap is a complete binary tree, where every parent has a key greater than or equal to (max heap) or less than or equal to (min heap) its child’s key.

Properties

• Height of a heap with n nodes: log2(n)+1
• Except for the last level, i-th level has 2^(i-1) nodes.
• Left child’s index = parent’s index * 2
• Right child’s index = parent’s index * 2 + 1
• Parent’s index = Child’s index/2

Insertion (upheap)

1. Insert the new element next to the last node
2. Keep exchanging with its parent until it satisfies max/min heap condition

Time complexity: height of a heap, O(log2(n))

Deletion (downheap)

1. Move the last element to the deleted node
2. Keep exchanging with its larger (smaller) child until it satisfies max (min) heap condition

Time complexity: height of a heap, O(log2(n))

Heap sort

Sorting algorithm which utilize heap structure. For n elements,

1. Add elements with upheap
2. Delete and pop element with downheap. Popped element is saved to the sorted array

Time complexity: For each element, maximum number of upheap or downheap operation is equal to the tree height, O(log2(n)) Total complexity for n elements: O(nlog2(n))

Implementation

Array can represent heap elements.

class Heap:
    '''
    Max Heap
    '''
    def __init__(self):
        self.list = [None] # to make root index 1

    def show(self):
        
        if len(self.list)==1:
            print('Empty heap')
        else:
            print('List:',self.list)
            h=int(np.log2(len(self.list)-1))+1
            for i in range(h):
                min_idx=2**i
                max_idx=min(len(self.list),2**(i+1))
                print('lvl {0}:'.format(i+1),self.list[min_idx:max_idx])
        

  # END OF HEAP HELPER METHODS
  
    def add(self, element):
        # Add
        self.list.append(element)
        
        # Upheap
        idx = len(self.list)-1
        while idx//2 > 0:
            child = self.list[idx]
            parent = self.list[idx//2]
            if parent < child:
                self.list[idx] = parent
                self.list[idx//2] = child
            idx = idx//2
            
    def delete(self):
        if len(self.list)<2:
            print('Empty heap')
        else:
            # Delete and Downheap
            max_element=self.list[1]
            #print("Remove: {0} from {1}".format(max_element, self.list))
            self.list[1] = self.list[-1]
            self.list.pop()
            
            #print(self.list)
            
            idx=1
            # loop as long as left child exists
            while idx*2<len(self.list):
                
                larger_child_idx = None
                # Get larger child index
                if (idx*2+1)>=len(self.list):
                    # Only left child
                    larger_child_idx = idx*2
                else:
                    left_child = self.list[idx*2]
                    right_child = self.list[idx*2+1]
                    if left_child>right_child:
                        larger_child_idx=idx*2
                    else:
                        larger_child_idx=idx*2+1
                
                child = self.list[larger_child_idx]
                parent = self.list[idx]
                #print('hi',child,parent,self.list)
                if parent<child:
                    self.list[idx]=child
                    self.list[larger_child_idx]=parent
                #else:
                    #break
                idx = larger_child_idx
                #print(idx,len(self.list))
                
            return max_element
        

def heap_sort(arr):
    
    arr_sorted=[]
    heap = Heap()
    
    for i in arr:
        heap.add(i)
        
    heap.show()
    while len(heap.list)>1:
        max_element = heap.delete()
        arr_sorted.insert(0, max_element)
    
    return arr_sorted

        
print('Sorted:',heap_sort([2,5,8,3,10,6,9,4,1,7,11]))
print('Sorted:',heap_sort([10,9,8,7,6,5,4,3,2,1]))
print('Sorted:',heap_sort([1,2,3,4,5,6,7,8]))

Output:

List: [None, 11, 10, 9, 4, 8, 5, 6, 2, 1, 3, 7]
lvl 1: [11]
lvl 2: [10, 9]
lvl 3: [4, 8, 5, 6]
lvl 4: [2, 1, 3, 7]
Sorted: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]
List: [None, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
lvl 1: [10]
lvl 2: [9, 8]
lvl 3: [7, 6, 5, 4]
lvl 4: [3, 2, 1]
Sorted: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
List: [None, 8, 7, 6, 4, 3, 2, 5, 1]
lvl 1: [8]
lvl 2: [7, 6]
lvl 3: [4, 3, 2, 5]
lvl 4: [1]
Sorted: [1, 2, 3, 4, 5, 6, 7, 8]