binary heap - how and when to use max-heapify

Question

i'm reading about the heap data structure, and i can't figure out when to use max heapify function and why.

I wrote a insert function that will always keep the heap a max-heap and i can't see when will max-heapify ever be used.

Can you please explain? Thank you

this is my code:

  int  PARENT(int i) {
    return i/2;
  }

  int LEFT(int i) {
    return 2*i;
  }
  
  int RIGHT(int i ) {
    return 2*i +1;
  }

  void max_heapify(int *v, int index, int heapsize) {
    int largest;
    int left = LEFT(index);
    int right = RIGHT(index);
  
    if (left<heapsize && v[left] > v[index])
      largest = left;
    else 
      largest = index;
  
    if (right < heapsize && v[right] > v[largest])
      largest = right;
  
    if (largest !=index) {
      v[index]  = v[index] ^v[largest];
      v[largest] = v[index] ^v[largest];
      v[index] = v[index] ^v[largest];
      max_heapify(v,largest,heapsize);
    }
  }

  void insert(int *v, int * length, int value) {
    v[++*length] = value;
    int valuePos = *length;
    int parent = PARENT(valuePos);

    if (parent!=valuePos) {
      while (v[parent] < v[valuePos]) {
        v[parent] = v[parent] ^ v[valuePos];
        v[valuePos] = v[parent] ^v[valuePos];
        v[parent] = v[parent] ^ v[valuePos];
        valuePos = parent;
        parent = PARENT(valuePos);
      }
    }
  }

Answer 1

The heapify algorithm should be used when turning an array into a heap. You could do that by inserting each array element in turn into a new heap, but that would take O(n lg n) time, while heapify does it in O(n) time.

Answer 2

max_heapify is expected to invoke on a regular array, to make it a heap. And insert does the maintenance work, which requires the array (v in your function) already being a heap.

Answer 3

The max-heapify function, as you call it, is a general heapify function (a heap can use any valid comparison function for sorting it's elements). It is intended to be used as an init function for constructing a heap from an array.

The complexities of functions for dealing with a heap (with their intented usages):

• init (max-heapify): O(n) , used to initialize a heap from a sorted sequence (array) (max-sorted, in your case)
• insert : O(lg n) , used to insert a single element in a heap (maintains the heap tree "sorted")
• delete : O(lg n) , used to remove a "best" (max, in your case) element from a heap (maintains the heap tree "sorted")

But, since this question is tagged C++, you should also consider using a std::set from STL instead of implementing your own heap. Complexities of the considered operations are the same as for any heap implementation, and it can easily operate with any comparison function (either pre-written or user-written). Another advantage against a heap implementation is that it is a sorted container, and you can easily iterate trough all the elements in the sorted order (not just the first one) without destroying the structure.

The only problem with std::set is that it is a unique container - meaning, only 1 copy of an element with a same key can exist in it. But there is a solution for that also - std::multiset keeps sorted instances of multiple objects with the same key.

Also, depending on your required usage (it there is a lot of data associated with the search key), you might also want to try std::map or std::multimap.

If you want to make your own heap implementation, I would strongly suggest putting it in a separate class (or even a namespace) if your intention is to use C++ to the fullest. If you just intend to keep the implementation in the form it is, you should consider re-tagging the question to C

Answer 4

You need to insert the data in heap randomly like in array. Afterwards u can call the max heapify function to keep the property of a Max Heap. Here is my code

class max_heap{  
 private:               // are the private members of class
      int *arr;
      int size;
      int ind;
};

        void max_heap::bubbledown(int *ar, int i)
        {
         int len = ind - 1;
         int lt = 2 * i;
         int rt = lt + 1;
         while (lt <= len && rt <= len)                                         
         {
            if (arr[i] > arr[lt] && arr[i] > arr[rt])
                break;

            else if (ar[lt] > ar[rt])
            {
                if (ar[i] < ar[lt]){
                    swap(ar[i], ar[lt]);
                    i = lt;
                    lt = 2 * i;
                }
            }
            else if (ar[lt] < ar[rt])
            {
                if (ar[i] < ar[rt]){
                    swap(ar[i], ar[rt]);
                    i = rt;
                    rt = (2 * i)+1;
                }
            }
        }
    }

    void max_heap::heapify()
    {
        int len = ind - 1;
        for (int i = len; i >= 1 && (i/2) >= 1; i--)
        {
            if (arr[i] > arr[i/2])
            {
                swap(arr[i], arr[i/2]);
                bubbledown(arr, i);
            }
        }
    }