Skip to main content

Heap Sort

Heap Sort is a sorting algorithm based on the heap data structure. A heap is a tree based data structure where the tree is a complete binary tree. A complete binary tree is a binary tree in which all levels are completely filled, except the last level which may or may not be complelety filled. Heaps can be of two types:

  • Max Heap: In max heap, every parent node must have value greater than or equal to it's child's value. 
  • Min Heap: In min heap, every parent node must have value less than it's child's value.
We are going to use the Max Heap for heap sort here. The sorting process includes: construction of a heap from the data, a max heap precisely, swapping of the first and last node, removing the last node from the heap and processing it for the remaining. With each cycle, the heap gets smaller and the list gets to sort. 

Illustration:

Algorithm:

  1. Construct max heap from the list
  2. Swap the first node with the last node
  3. Remove last node from heap
  4. Perform step 1 to 3 for the remaining heap
  5. Stop when heap empty   
heapSort(list)
    n=length of list       
    for i from n//2-1 to -1 with inverval of -1 
        heapify(list,n,i)
    for i from n-1 to 0 with interval -1
        Swap valueAtIndex_i with valueAtIndex_0
        heapify(list,i,0)
heapify(list,lengthofdata,i)
    largest=i
    leftchildIdx,l=2*i+1
    rightchildIdx,r=2*i+2   
    if l<lengthofdata and valueAtlargest < valueAtl:
        largest=l
    if r<lengthofdata and valueAtlargest < valueAtr
        largest=r
    if largest!=i:
        swap valueAti with valueAtlargest
        perform recursion(heapify root), heapify(list,lengthofdata,largest)

Time Complexity:

  • Worst Case: O(nlogn)
  • Average Case: O(nlogn)
  • Best Case: O(nlogn)

Space Complexity: O(1)

Program for Heap Sort:

Output:

Labels:

Popular posts from this blog

Coding Problem: Sober Walk

Our hoary culture had several great persons since time immemorial and king vikramaditya’s nava ratnas(nine gems) belongs to this ilk. They are named in the following shloka: Among these, Varahamihira was an astrologer of eminence and his book Brihat Jataak is recokened as the ultimate authority in astrology. He was once talking with Amarasimha,another gem among the nava ratnas and the author of Sanskrit thesaurus, Amarakosha. Amarasimha wanted to know the final position of a person, who starts from the origin 0 0 and travels per following scheme.     He first turns and travels 10 units of distance     His second turn is upward for 20 units     Third turn is to the left for 30 units     Fourth turn is the downward for 40 units     Fifth turn is to the right(again) for 50 units … And thus he travels, every time increasing the travel distance by 10 units. Code:
Read more

Image to Pencil Sketch using Python and OpenCV

In this post, we will go through a program to get a pencil sketch from an image using python and OpenCV.  Step 1:  To use OpenCV, import the library. Step 2: Read the Image. Step 3: Create a new image by converting the original image to grayscale. Step 4: Invert the grayscale image. We can invert images simply by subtracting from 255, as grayscale images are 8 bit images or have a maximum of 256 tones. Step 5: Blur the inverted image using GaussianBlur  method in OpenCV library and invert the blurred image.  Step 6: Divide the grayscale values of the image by the values of image received from step-5 ( Note: We inverted the grayscale image and we blurred this image and then again inverted it ). Diving an image from its smoothened form will highlight the edges and we get the image like Pencil Sketch. Steps Illustration: Code: Execution Output:
Read more