堆是一种特殊的树形数据结构，其每个节点都有一个值，通常提到的堆都是指一棵完全二叉树，根节点的值小于（或大于）两个子节点的值。同时，根节点的两棵子树也分别是一个堆。
堆排序是一种选择排序，在排序过程中，将 R[1···n] 看成是一棵完全二叉树的顺序存储结构，利用完全二叉树中双亲节点和子节点之间的内在关系来选择最小元素。
又大于或等于右子树的关键字值，那么这个堆被称之为大顶堆。此时，堆顶元素必为最大值。
如果根结点的关键字既小于或等于左子树的关键字值，又小于或等于右子树的关键字值，那么这个堆被称之为小顶堆。此时，堆顶元素必为最小值。
堆排序的思想是对于给定的n个记录，初始时把这些记录看作一棵顺序存储的二叉树，然后将其调整为一个大顶堆，再将堆的最后一个元素与堆顶元素(即二又树的根结点)进行交换后，堆的最后一个元素即为最大记录。
接着将前(n-1)个元素(即不包括最大记录)重新调整为一个大顶堆，再将堆顶元素与当前堆的最后一个元素进行交换后得到次大的记录。
重复该过程直到调整的堆中只剩一个元素时为止，该元素即为最小记录，此时可得到一个有序序列。
（1）将初始待排关键字序列 R[1…n] 构建成大顶堆，此堆为初始的无序区。
（3）由于交换后新的堆顶 R[1] 可能违反大顶堆的性质，因此需要对当前无序区 R[1…n-1]调整为大顶堆，然后再次将 R[1] 与无序区最后一个元素交换，得到新的无序区R[1…n-2]和新的有序区R [n，n-1]。
（4）不断重复此过程直到有序区的元素个数为(n-1)，则整个排序过程完成。