What does it actually mean by different heap-operations?

There are various heap-operations and various names are given to some same operations.

I am overwhelmed by the names and aliases.

So please clarify, What are the differences/similarities/relationships among the following heap-operations:

(1) Heapify
(2) Insert
(3) Delete
(4) Shift-up
(5) Shift-down

For example, some resources talk about implementing Heapsort using shift-down; while some implemented the same algorithm using Heapify. S开发者_如何学运维ome even implemented it using Delete.

1) Heapify restores the heap condition. For example if you changed a node in the tree the condition isn't valid anymore. You can restore the condition if you move your nodes up or down the tree.

2) Insert a node in the tree

3) Delete a node in the tree

4) Move a node up in the tree, as long as needed (depending on the heap condition: min-heap or max-heap)

5) Move a node down in the tree, similar to 4)

It's probably best if you try to implement or understand real code and don't worry about the naming..

Take a peek over at Wikipedia and you can get all sorts of information on heaps:

http://en.wikipedia.org/wiki/Heap_%28data_structure%29

To add a note to answer by @duedl0r, what shift up and shift down are used for is heapify the current structure. So for eg. in case of min heap, when you insert the element which is less than some nodes in the tree, the data structure now doesn't follow heap condition (in case of min heap, value of parent should be less than its children), so you have to shift up and up.

So in terms of code :

public void insert(int value) {
    if (heapSize == data.length)
        throw new HeapException("Heap's underlying storage is overflow");

    else {
        heapSize++;
        data[heapSize - 1] = value;
        siftUp(heapSize - 1);
    }

}    

private void siftUp(int nodeIndex) {
    int parentIndex, tmp;
    if (nodeIndex != 0) {
        parentIndex = getParentIndex(nodeIndex);
        /*if parent index data is more than child data, swap*/
        if (data[parentIndex] > data[nodeIndex]) {
            tmp = data[parentIndex];
            data[parentIndex] = data[nodeIndex];
            data[nodeIndex] = tmp;
            siftUp(parentIndex);
        }
    }

}

data is the array to resemple heap, and heapSize is current place where new element will be stored, and it tells that this much heap is full.

Similarly in case of delete you have to use shift down to restructure your heap.

By splitting heapify logic into shiftUp and shiftDown, we can reduce comparisons while inserting elements.

insert -> shift up -> only one comparison (with its parent)

remove -> shift down -> two comparison (with its left and right child's)

https://discuss.codecademy.com/t/what-are-some-differences-between-heapify-up-and-heapify-down/375384