浙江省建设工程协会网站,新楼盘网站模板,东莞p2p网站开发价钱,自有服务器 建网站1.堆 如果有一个关键码的集合 K { #xff0c; #xff0c; #xff0c; … #xff0c;}#xff0c;把它的所有元素按完全二叉树的顺序存储方式存储 在一个一维数组中#xff0c;则称为小堆( 或大堆 ) 。将根节点最大的堆叫做最大堆或大根堆#xff0c;根节点最小的…1.堆 如果有一个关键码的集合 K { … }把它的所有元素按完全二叉树的顺序存储方式存储 在一个一维数组中则称为小堆( 或大堆 ) 。将根节点最大的堆叫做最大堆或大根堆根节点最小的堆叫做最小堆或小根堆。 堆的性质 堆中某个节点的值总是不大于或不小于其父节点的值 堆总是一棵完全二叉树。 创建堆
向上调整建堆 向下调整建堆 堆的插入 先插入一个10到数组的尾上再进行向上调整算法直到满足堆 向上调整算法
数组一个个循环插入时边插入边成堆当插入新的元素时向上调整成新的堆
使用向上调整算法每次孩子与父亲相比较当孩子大于或小于父亲时进行交换改变孩子的下标再次进行判断然后交换知道孩子的下标为0 堆的删除 向下调整算法 给出一个数组逻辑上看做一颗完全二叉树。通过从根节点开始的向下调整算法可以把它调整成一个小堆。向下调整算法有一个前提左右子树必须是一个堆才能调整。 当已经成大堆或者小堆后想删元素最好的办法是把堆的第一个元素与最后一个进行交换当交换完成堆中最大或最小的元素就到了最后一个结点减小下标进行删除此时堆顶的左右子树为大堆或者小堆用向下调整算法将父亲与孩子循环比较大小进行交换形成新的堆再次把堆顶元素与最后一个元素交换使用向下调整成新的堆反复进行即可删除堆 堆的排序 升序 降序
向上调整建堆堆顶元素与最后一个元素交换再次向上或向下调整得到升序或降序
向上调整建堆 向下调整建堆 向上向下调整对比
向下调整时间复杂度分析 向上调整时间复杂度分析 总结 堆排序时间复杂度 堆的代码实现
//头文件
#pragma once
#includestdio.h
#includestdlib.h
#includeassert.h
#includestdbool.htypedef int HPDataType;
typedef struct Heap
{HPDataType* a;int size;int capacity;
}Heap;
//初始化
void HeapInit(Heap* hp);
// 堆的销毁
void HeapDestory(Heap* hp);
// 堆的插入
void HeapPush(Heap* hp, HPDataType x);
// 堆的删除
void HeapPop(Heap* hp);
// 取堆顶的数据
HPDataType HeapTop(Heap* hp);
// 堆的数据个数
int HeapSize(Heap* hp);
// 堆的判空
bool HeapEmpty(Heap* hp);
//向上调整
void Adjustup(HPDataType* a, int child);
//向下调整
void Adjustdown(HPDataType* a, int parent);
void swap(Heap* hp, int child, int parent);//函数实现
#define _CRT_SECURE_NO_WARNINGS 1
#pragma warning(disable:6031)
#includeheap.h
//初始化
void HeapInit(Heap* hp)
{assert(hp);hp-a NULL;hp-size hp-capacity 0;
}
void swap( int *p1, int *p2)
{int tmp *p1;*p1 *p2;*p2 tmp;
}
bool HeapEmpty(Heap* hp)
{assert(hp);return hp-size 0;
}// 堆的销毁
void HeapDestory(Heap* hp)
{free(hp-a);hp-a NULL;free(hp);hp NULL;
}
//向上调整
void Adjustup(HPDataType* a, int child)
{assert(a);int parent (child - 1) / 2;while (child 0){if (a[child] a[parent]){swap(a[child], a[parent]);child parent;parent (child - 1) / 2;}else {break;}}
}
// 堆的插入
void HeapPush(Heap* hp, HPDataType x)
{assert(hp);if (hp-capacity hp-size)//1未开劈空间 2.已满没有空间{int newcapacity hp-capacity 0 ? 4 : hp-capacity * 2;Heap* tmp (Heap*)realloc(hp-a, sizeof(HPDataType)* newcapacity);if (tmp NULL){perror(realloc fail);return NULL;}hp-a tmp;hp-capacity newcapacity;}//空间够 hp-a[hp-size] x;hp-size;//放进之后 向上调整形成新的堆Adjustup(hp-a, hp-size - 1);
}
//向xia调整
void Adjustdown(HPDataType* a,int n, int parent)
{assert(a);int child parent * 2 1;while (child n){ //右孩子小于huo大于左孩子if (child 1 n a[child 1] a[child]){child;}if (a[parent] a[child]){swap(a[child], a[parent]);parent child;child parent * 2 1;}else {break;}}
}
// 堆的删除
void HeapPop(Heap* hp)
{assert(hp);assert(!HeapEmpty(hp));//把第一个元素与最后一个交换向下调整swap( hp-a[0],hp-a[hp-size-1]);hp-size--;Adjustdown(hp-a, hp-size, 0);}
//取堆顶数据
HPDataType HeapTop(Heap* hp)
{assert(hp);assert(!HeapEmpty(hp));return hp-a[0];
}
// 堆的数据个数
int HeapSize(Heap* hp)
{assert(hp);return hp-size;
}
#define _CRT_SECURE_NO_WARNINGS 1
#pragma warning(disable:6031)
#includeheap.h
void test()
{Heap hp;HeapInit(hp);int a[] { 60,50,6,8,14,7,3 };for (int i 0; i sizeof(a) / sizeof(a[0]); i){HeapPush(hp, a[i]);}HeapDestroy(hp);
}
void HeapSort(int* a, int n)
{// 升序 -- 建大堆// 降序 -- 建小堆Heap hp;HeapInit(hp);//建堆--向上调整建堆/*for (int i 1; i n; i){AdjustUp(a, i);}*/// 建堆--向下调整建堆 --O(N)for (int i (n - 1 - 1) / 2; i 0; --i){AdjustDown(a, n, i);}int end n - 1;while (end 0){Swap(a[0], a[end]);// 再调整选出次小的数AdjustDown(a, end, 0);--end;}
}
int main()
{test();return 0;
}
