算法导论——(二叉)堆和堆排序

这篇笔记不知道该发在acm还是数据结构,就数据结构吧。。
今天数电课还是挺有收获的,至少认识到3个知识点:1、原来一直认为单片机是早期的cpu,现在才知道整个单片机应当是mcu(微控制单元,以前一直以为mcu==cpu),而cpu是mcu的核心;2、单片机的RAM是SRAM,呵呵,原来是cache,怪不得这么快。。3.位异或可以看成单个位之间的相加,第一次听到这种理解,颇有醍醐灌顶之感。
好吧,还是来说说正题,关于堆.
1.(二叉)堆是完全二叉树
2.堆的高度:从下往上(最下面一层高度为0)(从0开始)。
3.高度与
4.约定:用一维数组存储堆,根是heap[1]
5.高度h和元素个数n的关系:h=floor(log(n))
6.如何将无序数组建成大根堆:对非叶子节点从下往上保持堆一遍
7.实现《算法导论》中的伪代码

//注意:二叉堆的根是heap[1];
#include<stdio.h>
#include<stdlib.h>
int heap[7];
int heapsize,length=6;
void max_heapify(int *heap,int i);
void build_max_heap(int *heap);
void heapsort(int *heap);
int main()
{
	/*
	int i=1,j=8;
	while(i<=6)
	{
		heap[i]=j--;
		i++;
	}
	build_max_heap(heap);
	heapsort(heap);
	for(i=1;i<=6;i++)
		printf("%d ",heap[i]);
	printf("\n");
	*/
	system("pause");
	return 0;
}
void max_heapify(int *heap,int i)//根节点与孩子关系未确定,但子树都是堆
{
	int largest;
	int l=2*i,r=2*i+1;
	if(l<=heapsize&&heap[l]>heap[i])
		largest=l;
	else
		largest=i;
	if(r<=heapsize&&heap[r]>heap[largest])
		largest=r;
	if(largest!=i)
	{
		int t;
		t=heap[i];
		heap[i]=heap[largest];
		heap[largest]=t;
		max_heapify(heap,largest);
	}
	return;
}
void build_max_heap(int *heap)//将无序数组建成二叉堆
{
	heapsize=length;
	int i;
	for(i=heapsize/2;i>=1;i--)
	{
		max_heapify(heap,i);
	}
	return;
}
//二叉排序
void heapsort(int *heap)//排序后为升序
{
	int i;
	for(i=length;i>=2;i--)
	{
		int t;
		t=heap[i];
		heap[i]=heap[1];
		heap[1]=t;
		heapsize--;
		max_heapify(heap,1);
	}
	return;
}

事实上,堆排序虽漂亮,但快排往往优于它,而且C++ STL中的sort()的内部就是快排,所以直接调用即可。

发表评论

电子邮件地址不会被公开。 必填项已用 * 标注

*

您可以使用这些 HTML 标签和属性: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>