主要测试大堆,测试源码在(github)
堆
堆可以看成一个近似的完全二叉树,除了底层外,该树是完全充满的,而且是从左到右填充。
完全二叉树适合用数组来存储。用数组来存储完全二叉树是非常节省存储空间的。å
最大堆中,是指除了根结点外(根结点没有 parent),所有结点的 i 都应该满足:
堆被看作是一个完全二叉树,那么该堆堆高度成正比O(lgn),我们会发现,堆结构上的一些基本操作的运行时间至多与树的高度成正比,即实际复杂度为O(lgn)。
堆排序过程:
MAX-HEAPIFY(堆化):将堆的末端子节点作调整,使得子节点永远小于父节点。
BUILD-MAX-HEAD(建堆):从无序数据数组中构造一个最大堆。
HEAPSORT(排序):对数组进行原址排序,移除位在第一个数据的根节点,并做最大堆调整的递归运算。
堆化
堆化让数值大的结点往上浮,让小的结点逐渐下沉。
堆化流程.png
堆化伪代码
void max_heapify(int array[], int size, int i) {
int largest = i;
int l = left(i);
int r = right(i);
if (l <= size && array[l] > array[i]) {
largest = l;
}
if (r <= size && array[r] > array[largest]) {
largest = r;
}
if (largest != i) {
swap(&array[largest], &array[i]);
max_heapify(array, size, largest);
}
}
建堆
我们可以通过二叉树结点自底向上的方法,利用堆化过程,把一个大小为 n = A.length 的数组 A = [1...n] 转换为最大堆。BUILD-MAX-HEAP 时间复杂度为 O(n)
建堆伪代码
void build_max_heap(int array[], int len) {
for (int i = (len / 2); i >= 1; i--) {
max_heapify(array, len, i);
}
}
排序
BUILD-MAX-HEAP 会将数组A[1...n]建成最大堆。最大堆元素在根结点A[1],去掉 A[1] 后,A[1]的左右孩子结点仍然是最大堆。如果把 A[n] 替换 A[1],破坏了最大堆性质,将重新对 A[1...n-1] 数组进行堆化,使其变成最大堆。如此递归重复以上步骤。
排序流程
排序流程
void HeapSort::heap_sort() {
if (m_data_size <= 1) {
return;
}
// 建堆处理后,父结点 > 子结点
build_max_heap(m_array, m_data_size);
// 建堆后,堆顶结点(根结点)是最大数值,把最大值放到数组最后。原数组最后一个结点置换到根结点。
swap(&m_array[1], &m_array[m_data_size]);
// 排除数组最后一个元素,再对剩余堆进行堆化,再把堆化的根结点放到数组最后。
m_data_size--;
// 从上到下(父节点到子树结点)
while (m_data_size > 1) {
max_heapify(m_array, m_data_size, 1);
swap(&m_array[1], &m_array[m_data_size]);
m_data_size--;
}
}
优先队列
在计算机系统的作业调度中,任务需要根据优先级进行执行。可以根据堆算法(最大堆),每个任务都赋予一个优先级数值,选出最高优先级(最大堆堆顶)作业任务执行。涉及任务处理,一般都有增删改查的操作。
理解了建堆,堆化和排序的流程,队列的这些操作应该都比较好理解了。
HEAP-MAXINUM
获取堆顶元素,时间复杂度为
bool HeapSort::heap_maxinum(int& n) {
if (m_data_size <= 0) {
return false;
}
if (!m_is_build_heap) {
build_max_heap(m_array, m_data_size);
}
n = m_array[1];
return true;
}
HEAP-EXTRACT-MAX
删除堆顶元素,时间复杂度为
bool HeapSort::heap_extract_max(int& n) {
if (m_data_size <= 0) {
return false;
}
if (!m_is_build_heap) {
build_max_heap(m_array, m_data_size);
}
n = m_array[1];
swap(&m_array[1], &m_array[m_data_size]);
m_data_size--;
max_heapify(m_array, m_data_size, 1);
return true;
}
HEAP-INCREAASE-KEY
增加堆指定元素(任务)的数值,HEAP-INCREAASE-KEY 时间复杂度为
bool HeapSort::heap_increase_key(int i, int key) {
if (i < 1 || m_data_size <= 0 || key < m_array[i]) {
return false;
}
if (!m_is_build_heap) {
build_max_heap(m_array, m_data_size);
}
// 这里跟 build_max_heap 道理一样,只是 build_max_heap
// 是自底向上,heap_increase_key 是从 i 结点向上
m_array[i] = key;
while (parent(i) > 0 && m_array[parent(i)] < m_array[i]) {
swap(m_array[parent(i)], m_array[i]);
i = parent(i);
}
return true;
}
MAX-HEAP-INSERT
插入新元素到最大堆末位,也就是在最大堆上增加一个叶子,叶子自下而上与它的父结点比较替换。运行时间复杂度为
bool HeapSort::max_heap_insert(int key) {
if (m_data_size >= m_data_len) {
return false;
}
if (!m_is_build_heap) {
build_max_heap(m_array, m_data_size);
}
// 将结点放置数组末位,也就是在最大堆上增加一个叶子,叶子自下而上与它的父结点比较替换。
m_data_size++;
m_array[m_data_size] = key;
// 这是 heap_increase_key 主逻辑的实现。
int i = m_data_size;
while (parent(i) > 0 && m_array[parent(i)] < m_array[i]) {
swap(m_array[parent(i)], m_array[i]);
i = parent(i);
}
return true;
}
参考
现在发现,单纯看《算法导论》很难看懂文章内容,可以先从其它的帖子中理解算法的逻辑,在对算法有一定的理解的基础上,再结合书本内容,才能更好理解书本内容。
wiki
《算法导论》第六章 堆排序
堆和堆排序:为什么说堆排序没有快速排序快
更精彩内容,请关注我的博客:https://wenfh2020.com
网友评论