首页 > 代码库 > 堆和堆排序
堆和堆排序
一，优先级队列
数据集合中，各元素的访问顺序取决于元素自身的优先级(call-by-priority)，
二，拥有的操作接口
1.插入操作
2.获取优先级最高的元素
3.删除优先级最高的元素
三，最基本的堆操作
1.下虑
void percolateDown(int heap[],int start,int end){ int temp = heap[start]; for (int j = 2 * start + 1 ; j < end ; j = 2 * j + 1) { while (j<end-1 && heap[j] <heap[j+1]) { j++; } if(temp >=heap[j]) break; heap[start] = heap[j]; start = j; } heap[start] = temp; }
2.上虑
void percolateUp(int heap[],int start){ int temp=0; int j = 0; while (start>0) { temp = heap[start]; j = (start - 1)/2; if (heap[start]>heap[j]) { heap[start]=heap[j]; heap[j]=temp; start=j; }else{ break; } }}
3.删除堆顶元素
int delete(int heap[],int *length){ if (heap == NULL) { return 0; } heap[0] = heap[*length-1]; (*length)--; percolateDown(heap, 0, *length); return 1; }
4.在堆顶插入元素
int insert(int heap[],int value,int * length){ if (heap == NULL) { return 0; } heap[*length] = value; percolateUp(heap, *length); (*length)++; return 1;}
5.创建一个堆
int createHeap(int heap[],int length){ if (heap == NULL || length == 0) { return 0; } for (int i = length / 2 -1; i>=0; i--) { percolateDown(heap, i, length); } return 1;}
堆和堆排序
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。