A heap (as used in heap sort) is a binary tree where each node has (at most) two child nodes.
The bottom row of the heap is always filled from left to right.
Every node forms a sub-heap -- all the values that descend from that node.
Since a heap is completely fixed, it can be mapped to a linear array
The children of a parent node are always at 2*index and 2*index+1 (or 2*index+1 and 2*index+2 if your arrays start from 0)
The last parent node is always exactly half way through the heap.
If each parent is equal to or greater than both it's children, then the heap is called "correct".
If one or more children are a greater than their parent, then the heap is called "incorrect".
A node without children is correct.
You can remove the last element on the bottom right of a correct heap, and you will still have a correct heap.
Every parent node in a correct heap is equal to or greater than all it's descendants (all values beneath it in the heap).
The top element is always the greatest element in a correct heap.
Heap Sort often adds these utility functions, presumably so the heap can be used as a database.
Here are general utility functions that operate on the heap
Add Element.
Elements are always added to the end of the heap (the first empty space on the bottom row).
Sift-Up
After adding an element, the heap is probably incorrect.
Calling Sift Up corrects the heap.
Sift Up compares a node to it's parent.
If the element is smaller than it's parent (or it's the top of heap) then done.
Else, the node is swapped and Sift Up is executed on the parent node.
Once upon a time, heap sort started with an empty heap and added all elements to create a correct heap.
It's slower and requires more code than Heapify, but it works.
Sift-Down
Like Sift Up, Sift Down fixes an incorrect heap.
Starting with the parent of two correct child nodes;
If the parent is equal to or greater than both child nodes, then the heap is correct.
If not, then swap the parent with the greatest child node. Now the new parent node is greater than both child nodes.
Go to the child node you swapped with, and repeat the procedure.
Continue until either the parent is already greater when sifted down (no swap necessary) or you reach the bottom of the heap.
Remove Element
Remove an element from the middle of the heap, and then fix the heap.
If you remove the last element (right most on the bottom row) the heap is still correct.
To remove an element from the middle of the heap, you replace it with the last element, then call both Sift Up and Sift Down on the node.
Heapify
Heapify changes a random heap into a correct heap.
Starting with the last parent node and working backwards to the top, call sift down on each node.
Heapify is an O(N) operation. -- This page explains in detail.
Theoretically, you could use Heapify to create a correct heap in O(N) time, then search the heap for values in O(log N) time.
I suppose there might be some reason to do this rather than using an associative array (a.k.a. hashing), but none come to mind.