//序：希望完成5个后，放在github..作为自己 写过的程序！
//来源：http://blog.csdn.net/lalor/article/details/7370542
|
|
处理了 unistd.h times.h |
|
| mark | memcpy(data1,data,(MAX+1)*sizeof(int));//66 add for sort |
|
|
| beg=clock();//其他有需要，有更精密的计时。 (end- beg)*1000 /CLOCKS_PER_SEC ); | CLOCKS_PER_SEC 什么？ |
| 下一个月 | std::sort(data1+1, data1+MAX+1); | Std::Sort 实现思路 |
| 品味 | siftdown如何退出递归的（）
堆 调整的时候 是如何调用siftdown
siftdown算法 是如何 找出 最大的节点（包括叶节点的） |
|
| 编程小结 | 好的算法 是不用背的，，要找到亮点，逐类旁通 才是掌握。 算法中分支， 今天总在 琢磨， 幸运的分支是？？ 不幸运的分支？ siftdown 找最大的，幸运是马上就是叶节点（退出），不然要看左节点，还要看右节点（个人观点）
当 编程也带上了感情色彩@@呵呵 |
|
#include "stdafx.h"
#include "完工.h"
#include "stdio.h"
using namespace std;
#include <iostream>
#include <fstream> // 66 add
#include "time.h"
#include <algorithm>
#include "unistd.h" //66 add
#include "stdlib.h"
#include "times.h" //66 new add
#define PARENT(I) (I/2)
#define LEFT(I) (2*I)
#define RIGHT(I) (2*I+1)
int HEAP_SIZE;
int ARR_LENGTH;
/************************************************************************/
/* */
/************************************************************************/
#define MAX 100000 // 10W
void mysiftdown(int *data,int i);
void 建堆(int *data);
//void mysiftup(int *data);
void myHeapSort(int *data);
void mysiftdown(int *data,int i);
void mysiftup(int *data);
void myHeapSort(int *data);
void swap(int *data,int i,int j){
int tmp=data[i];
data[i]=data[j];
data[j]=tmp;
}
//主程序
void 珠儿_heap()
/************************************************************************/
/* 2012-3-30 19:53:26 //作者改编版本，没有使用up,down.
一个月写一次，下一次，使用原版本的。
解决windows 下unistd.. 换用c库中计时函数，精度在ms.
想法：可否在最外面写成一个循环，while cin>>file.... 测试多组的规律
*/
/************************************************************************/
{
int data[MAX+1]; //in c++ ,can change it!
int data1[MAX+1];
int i;
int temp;
long beg,end;
time_t begTms,endTms;
/************************************************************************/
/* 模拟输入1/3
2012-3-31 17:12:32 最粗心，没用sizeof for memcpy
*/
/************************************************************************/
srand( time(0));
ARR_LENGTH=MAX;
for (i=1;i<=MAX;i++)//data[0] 不用
{
data[i]=rand() %MAX;
}
memcpy(data1,data,(MAX+1)*sizeof(int));//66 add for sort
//2012年月日:03:29 尽然发现没有全部copy..仅复制了一部分.
//解决： sizeof
/************************************************************************/
/* 2/3 核心的 */
/************************************************************************/
beg=clock();//其他有需要，有更精密的计时。
myHeapSort(data);
//希望导出到文件。
end=clock();
printf("\n time cost %ld ms \n", (end- beg)*1000 /CLOCKS_[66771] PER_SEC );
/************************************************************************/
/* 3/3
看到这里的程序，我强烈怀疑这里的排序有没有意义！！
因为前面的指针已经排好了，所以这里排序有意义嘛？
解决：下面修正了，使用另外一个数组，
*/
/************************************************************************/
beg=clock();
std::sort(data1+1, data1+MAX+1[66772] );
//打印到文件
end=clock();
printf("\n time cost %ld ms \n", (end- beg)*1000 /CLOCKS_PER_SEC );
/************************************************************************/
/*
sort 函数好像有问题。解决方法：给原来的数组龙一个备份！！
还没有封转打印借口 */
/************************************************************************/}
//void my
void mysiftdown(int *data,int i){//66这个函数第一次调用初始堆也用，后面调整也用。
int l,r;
int largest;
l =LEFT(i);
r=RIGHT(i);
//compare its' left children and right children and it's seft
//find the largest element
if (l<=HEAP_SIZE && data[l]>data[i])
{
largest=l;
}
else{
largest=i;
}
//第三关
if (r<=HEAP_SIZE && data[r]>data[largest])
{
largest=r;
}
//if the largest is parent, then break
//else, continue heapify.
if (largest !=i)
{
swap(data,i,largest);
mysiftdown(data,largest);//66 递归，递归的出口是larget==i
}
//end
/************************************************************************/
/*
next 查证下珠儿是不是递归
*/
/************************************************************************/
}
void 建堆(int *data){
int i;
HEAP_SIZE=ARR_LENGTH;// 统一用一个宏的值.. max
//Here, assume data[ n/2+1, n] which is leaf node meet max heap's need
//then ,just adjust other element
for (i=ARR_LENGTH/2; i>=1; i-- )
{
mysiftdown(data,i);//66 这个，让我想起了刘正鹏那本数据结构书。建立初始堆
}
}
void myHeapSort(int *data){
int i;
建堆(data);
//extract the largest element from heap once per iterator
//heap'size will decrease, and keep it's attribute
for ( i=ARR_LENGTH ;i >=2; i--)
{
swap(data ,1 ,i); //
HEAP_SIZE--; //66 !!
mysiftdown(data,1);
}
//写完所有的函数，我怀疑书上的版本有没有siftdown? 2012-3-30 21:34:50
//ok 60%功能的heap 完工
}
源文档 <file:///C:\Documents%20and%20Settings\Administrator\桌面\新建%20Microsoft%20Office%20Word%20文档.docx>