Introduction to Algorithms by Thomas H. Cormen, Charles E. Leiserson and Ronald L. Rivest and Clifford Stein : Chapter 6

The author defines heap data structure as an array object which is a nearly complete binary tree. The authors provide two kinds of heaps, max heap which satisfies the heap property $ A[PARENT[i]] >= A[i] $ and min heap which satisfies the heap property $ A[PARENT[i]] <= A[i] $. The height of a node is defined to be the number of edges on the longest simple downward path from a node to a leaf. The height of the heap is defined to be the height of the root.

The authors provide an algorithm to heapify an array starting from index $ i $. The running time of this algorithm is proved to be $ O(\lg n) $. Using the heapify algorithm, authors give an algorithm to build a max heap and proves that it is linear.

The authors then provide an algorithm to sort an array using the algorithm to build heap and heapify. The authors prove that the algorithm takes $ O(n \times \lg n) $ time.

The authors then provide insert, get-max, extract-max and increase-key operations implemented on a priority queue and show that all the operations can be implemented in $ O(\lg n) $ time.