- #include <iostream>
- using namespace std;
- const length=100;
- int A[length]={1,9,10,2,7,5,6,4,13,3,18,11,100};
- int Heap_size(int A[]);//始终是数组内从后往前数的第一个非0数开始的一组数。
- int heap_size=Heap_size(A);
- int PARENT(int i);//父节点
- int LEFT(int i);//左孩子结点
- int RIGHT(int i);//有孩子结点
- void MAX_HEAPIFY(int A[],int i);//保持最大堆
- void BUILD_MAX_HEAP(int A[]);//建立最大堆
- void Print(int A[]);
- void Print1(int A[]);
- void HEAPSORT(int A[]);//最大堆排序
- int MAXIMUM(int A[]);
- int HEAP_EXTRACT_MAX(int A[]);//删除最大堆中的最大元素。
- void HEAP_INCREASE_KEY(int A[],int i,int key);//第i个位置的值增加为key
- void MAX_HEAP_INSERT(int A[],int key);
- void main()
- {
- int A[length]={1,9,10,2,7,5,6,4,13,3,18,11,100};
- cout<<"数组初始化:"<<endl;
- Print(A);
- cout<<"建立最大堆:"<<endl;
- BUILD_MAX_HEAP(A);
- Print(A);
- cout<<"删除最大堆的当前最大元素:"<<endl;
- HEAP_EXTRACT_MAX(A);
- Print(A);
- cout<<"最大堆第8位的数增加到15:"<<endl;
- HEAP_INCREASE_KEY(A,8,15);
- Print(A);
- cout<<"最大堆插入一个元素56:"<<endl;
- MAX_HEAP_INSERT(A,56);
- Print(A);
- cout<<"最大堆排序后的数组为:"<<endl;
- HEAPSORT(A);
- Print1(A);
- }
- int PARENT(int i)
- {
- return (i-1)/2;
- }
- int LEFT(int i)
- {
- return 2*i+1;
- }
- int RIGHT(int i)
- {
- return 2*i+2;
- }
- void MAX_HEAPIFY(int A[],int i)
- {
- int largest=0;
- int L=LEFT(i);
- int R=RIGHT(i);
- if (L<heap_size&&A[L]>A[i])
- {
- largest=L;
- }
- else largest=i;
- if (R<heap_size&&A[R]>A[largest])
- {
- largest=R;
- }
- if (largest!=i)
- {
- swap(A[i],A[largest]);
- MAX_HEAPIFY(A,largest);
- }
- }
- void BUILD_MAX_HEAP(int A[])
- {
- int heap_size=length;
- for (int i=length/2;i>=0;i--)
- {
- MAX_HEAPIFY(A,i);
- }
- }
- void HEAPSORT(int A[])
- {
- BUILD_MAX_HEAP(A);
- for (int i=Heap_size(A)-1;i>=0;i--)
- {
- swap(A[0],A[i]);
- heap_size--;
- MAX_HEAPIFY(A,0);
- }
- }
- int MAXIMUM(int A[])
- {
- return A[0];
- }
- int HEAP_EXTRACT_MAX(int A[])
- {
- if (heap_size<0)
- {
- cout<<"heap underflow"<<endl;
- exit(0);
- }
- int max=A[0];
- A[0]=A[heap_size-1];
- heap_size--;
- MAX_HEAPIFY(A,0);
- A[heap_size]=0;
- return max;
- }
- void HEAP_INCREASE_KEY(int A[],int i,int key)
- {
- if (key<A[i])
- {
- return ;
- }
- A[i]=key;
- while (i>0&&A[PARENT(i)]<A[i])
- {
- swap(A[i],A[PARENT(i)]);
- i=PARENT(i);
- }
- }
- void MAX_HEAP_INSERT(int A[],int key)
- {
- heap_size++;
- A[heap_size-1]=-0x7fffffff;
- HEAP_INCREASE_KEY(A,heap_size-1,key);
- }
- int Heap_size(int A[])
- {
- for (int i=length-1;i>=0;i--)
- {
- if (A[i]>0)
- {
- return i+1;
- }
- }
- return -1;
- }
- void Print(int A[])
- {
- for (int i=0;i<heap_size;i++)
- {
- if(A[i]>0)
- cout<<A[i]<<" ";
- }
- cout<<endl;
- }
- void Print1(int A[])
- {
- for (int i=0;i<length;i++)
- {
- if(A[i]>0)
- cout<<A[i]<<" ";
- }
- cout<<endl;
- }
下面是CSDN网友给的答案:这个代码完全忽略了边界问题,所以带来了一些错误问题下面是我基于网友给的代码基础上改的,经过我调整了多个函数的边界/条件后,用类的方法得以完美解决。
- //头文件
- /*#include <iostream>
- using namespace std;
- //宏定义
- #define N 1000
- #define PARENT(i) (i)>>1
- #define LEFT(i) (i)<<1
- #define RIGHT(i) ((i)<<1)+1
-
- class Heap
- {
- public:
- //成员变量
- int A[N+1];
- int length;
- int heap_size;
- //构造与析构
- Heap(){}
- Heap(int size):length(size),heap_size(size){}
- ~Heap(){}
- //功能函数
- void Max_Heapify(int i);
- void Build_Max_Heap();
- void HeapSort(int A[]);
- //优先队列函数
- void Heap_Increase_Key(int i, int key);
- void Max_Heap_Insert(int key);
- int Heap_Maximum();
- int Heap_Extract_Max();
- void Heap_Delete(int i);
- //辅助函数
- void Print();
- void Print1();
- };
-
- //使以i结点为根结点的子树成为堆,调用条件是确定i的左右子树已经是堆,时间是O(lgn)
- //递归方法
- void Heap::Max_Heapify(int i)
- {
- //Print();
- int l = LEFT(i), r = RIGHT(i), largest;
- //选择i、i的左、i的右三个结点中值最大的结点
- if(l < heap_size && A[l] > A[i])
- largest = l;
- else largest = i;
- if(r < heap_size && A[r] > A[largest])
- largest = r;
- //如果根最大,已经满足堆的条件,函数停止
- //否则
- if(largest != i)
- {
- //根与值最大的结点交互
- swap(A[i], A[largest]);
- //交换可能破坏子树的堆,重新调整子树
- Max_Heapify(largest);
- }
- }
-
- //建堆,时间是O(nlgn)
- void Heap::Build_Max_Heap()
- {
- heap_size = length;
- //从堆中最后一个元素开始,依次调整每个结点,使符合堆的性质
- for(int i = length / 2; i >= 0; i--)
- Max_Heapify(i);
- }
-
- //堆排序,时间是O(nlgn)
- void Heap::HeapSort(int A[])
- {
- //建立一个最大堆
- Build_Max_Heap();
- //每次将前i个元素构成最大堆
- for(int i = length-1; i >= 1; i--)
- {
- //将前i个元素中的最大值存入到A[i]中
- swap(A[0], A[i]);
- //堆的大小减一
- heap_size--;
- //只有堆顶的性质可能会被破坏
- Max_Heapify(0);
- }
- }
-
- //将元素i的关键字增加到key,要求key>=A[i]
- void Heap::Heap_Increase_Key(int i, int key)
- {
- if(key < A[i])
- {
- cout<<"new key is smaller than current key"<<endl;
- exit(0);
- }
- A[i] = key;
- //跟父比较,若A[PARENT(i)]<A[i],则交换
- //若运行到某个结点时A[PARENT(i)]<A[i],就跳出循环
- while(A[PARENT(i)] > 0 && A[PARENT(i)] < A[i])
- {
- swap(A[PARENT(i)], A[i]);
- i = PARENT(i);
- }
- }
-
- //把key插入到集合A中
- void Heap::Max_Heap_Insert(int key)
- {
- if(heap_size == N)
- {
- cout<<"heap is full"<<endl;
- exit(0);
- }
- heap_size++;length++;
- A[heap_size-1] = -0x7fffffff;
- Heap_Increase_Key(heap_size-1, key);
- }
- //返回A中最大关键字,时间O(1)
- int Heap::Heap_Maximum()
- {
- return A[0];
- }
- //去掉并返回A中最大关键字,时间O(lgn)
- int Heap::Heap_Extract_Max()
- {
- if(heap_size < 0)
- {
- cout<<"heap underflow"<<endl;
- exit(0);
- }
- //取出最大值
- int max = A[0];
- //将最后一个元素补到最大值的位置
- A[0] = A[heap_size-1];
- heap_size--;
- //重新调整根结点
- Max_Heapify(0);
- //返回最大值
- return max;
- }
- //删除堆中第i个元素
- void Heap::Heap_Delete(int i)
- {
- if(i > heap_size)
- {
- cout<<"there's no node i"<<endl;
- exit(0);
- }
- //把最后一个元素补到第i个元素的位置
- int key = A[heap_size-1];
- heap_size--;
- //如果新值比原A[i]大,则向上调整
- if(key > A[i])
- Heap_Increase_Key(i, key);
- else//否则,向下调整
- {
- A[i] = key;
- Max_Heapify(i);
- A[heap_size]=0;
- }
- }
-
- void Heap::Print()
- {
- int i;
- for(i = 0; i < heap_size; i++)
- {
- if(i > 0)cout<<',';
- else cout<<"==> A = {";
- cout<<A[i];
- }
- cout<<'}'<<endl;
- }
- void Heap::Print1()
- {
- int i;
- cout<<"==> A = {";
- for(i = 0; i < length; i++)
- {
- if (A[i]>0)
- {
- cout<<A[i]<<" ";
- }
- }
- cout<<'}'<<endl;
- }
- void main()
- {
- Heap a(13);
- a.A[0]=1;a.A[1]=9;a.A[2]=10;a.A[3]=2;a.A[4]=7;
- a.A[5]=5;a.A[6]=6;a.A[7]=4;a.A[8]=13;a.A[9]=3;
- a.A[10]=18;a.A[11]=11;a.A[12]=100;
- a.Build_Max_Heap();
- a.Print();
- a.Heap_Delete(2);
- a.Print();
- a.Heap_Extract_Max();
- a.Print();
- a.Heap_Increase_Key(8,15);
- a.Print();
- a.Max_Heap_Insert(56);
- a.Print();
- a.HeapSort(a.A);
- a.Print1();
- }
下面是6.5-3课后题引申的最小堆问题下面是不带类的C++代码
- #include <iostream>
- using namespace std;
- const length=100;
- int A[length]={1,9,10,2,7,5,6,4,13,3,18,11,100};
- int PARENT(int i);//父节点
- int LEFT(int i);//左孩子结点
- int RIGHT(int i);//有孩子结点
- void MIN_HEAPIFY(int A[],int i);//保持最小堆
- void BUILD_MIN_HEAP(int A[]);//建立最小堆
- void Print(int A[]);
- void Print1(int A[]);
- int Heap_size(int A[]);//始终是数组内从后往前数的第一个非0数开始的一组数。void HEAPSORT(int A[]);//最小堆排序
- void HEAPSORT(int A[]);
- int MINIMUM(int A[]);
- int HEAP_EXTRACT_MIN(int A[]);//删除最大堆中的最小元素。
- void HEAP_INCREASE_KEY(int A[],int i,int key);//第i个位置的值增加为key
- void MIN_HEAP_INSERT(int A[],int key);
- int heap_size=Heap_size(A);
- void main()
- {
- cout<<"数组初始化:"<<endl;
- Print(A);
- cout<<"建立最小堆:"<<endl;
- BUILD_MIN_HEAP(A);
- Print(A);
- cout<<"删除最小堆的当前最小元素:"<<endl;
- HEAP_EXTRACT_MIN(A);
- Print(A);
- cout<<"最小堆第8位的数增加到15:"<<endl;
- HEAP_INCREASE_KEY(A,8,15);
- Print(A);
- cout<<"最小堆插入一个元素56:"<<endl;
- MIN_HEAP_INSERT(A,56);
- Print(A);
- cout<<"最小堆排序后的数组为:"<<endl;
- HEAPSORT(A);
- Print1(A);
- }
- int PARENT(int i)
- {
- return (i-1)/2;
- }
- int LEFT(int i)
- {
- return 2*i+1;
- }
- int RIGHT(int i)
- {
- return 2*i+2;
- }
- void MIN_HEAPIFY(int A[],int i)
- {
- int largest=0;
- int L=LEFT(i);
- int R=RIGHT(i);
- if (L<heap_size&&A[L]<A[i])
- {
- largest=L;
- }
- else largest=i;
- if (R<heap_size&&A[R]<A[largest])
- {
- largest=R;
- }
- if (largest!=i)
- {
- swap(A[i],A[largest]);
- MIN_HEAPIFY(A,largest);
- }
- }
- void BUILD_MIN_HEAP(int A[])
- {
- int heap_size=length;
- for (int i=length/2;i>=0;i--)
- {
- MIN_HEAPIFY(A,i);
- }
- }
- void HEAPSORT(int A[])
- {
- BUILD_MIN_HEAP(A);
- for (int i=Heap_size(A)-1;i>=1;i--)
- {
- swap(A[0],A[i]);
- heap_size--;
- MIN_HEAPIFY(A,0);
- }
- }
- int MINIMUM(int A[])
- {
- return A[0];
- }
- int HEAP_EXTRACT_MIN(int A[])
- {
- if (heap_size<0)
- {
- cout<<"heap underflow"<<endl;
- exit(0);
- }
- int min=A[0];
- A[0]=A[heap_size-1];
- heap_size--;
- MIN_HEAPIFY(A,0);
- A[heap_size]=0;
- return min;
- }
- void HEAP_INCREASE_KEY(int A[],int i,int key)
- {
- if (key<A[i])
- {
- return ;
- }
- A[i]=key;
- while (i>0&&A[PARENT(i)]>A[i])
- {
- swap(A[i],A[PARENT(i)]);
- i=PARENT(i);
- }
- }
- void MIN_HEAP_INSERT(int A[],int key)
- {
- heap_size++;
- A[heap_size-1]=-0x7fffffff;
- HEAP_INCREASE_KEY(A,heap_size-1,key);
- }
- int Heap_size(int A[])
- {
- for (int i=length-1;i>=0;i--)
- {
- if (A[i]>0)
- {
- return i+1;
- }
- }
- return -1;
- }
- void Print(int A[])
- {
- for (int i=0;i<heap_size;i++)
- {
- if(A[i]>0)
- cout<<A[i]<<" ";
- }
- cout<<endl;
- }
- void Print1(int A[])
- {
- for (int i=0;i<length;i++)
- {
- if(A[i]>0)
- cout<<A[i]<<" ";
- }
- cout<<endl;
- }
下面是带类的C++最小堆代码:- //头文件
- /*#include <iostream>
- using namespace std;
- //宏定义
- #define N 1000
- #define PARENT(i) (i)>>1
- #define LEFT(i) (i)<<1
- #define RIGHT(i) ((i)<<1)+1
-
- class Heap
- {
- public:
- //成员变量
- int A[N+1];
- int length;
- int heap_size;
- //构造与析构
- Heap(){}
- Heap(int size):length(size),heap_size(size){}
- ~Heap(){}
- //功能函数
- void Min_Heapify(int i);
- void Build_Min_Heap();
- void HeapSort(int A[]);
- //优先队列函数
- void Heap_Increase_Key(int i, int key);
- void Min_Heap_Insert(int key);
- int Heap_Minimum();
- int Heap_Extract_Min();
- void Heap_Delete(int i);
- //辅助函数
- void Print();
- void Print1();
- };
-
- //使以i结点为根结点的子树成为堆,调用条件是确定i的左右子树已经是堆,时间是O(lgn)
- //递归方法
- void Heap::Min_Heapify(int i)
- {
- //Print();
- int l = LEFT(i), r = RIGHT(i), largest;
- //选择i、i的左、i的右三个结点中值最小的结点
- if(l < heap_size && A[l] < A[i])
- largest = l;
- else largest = i;
- if(r < heap_size && A[r] < A[largest])
- largest = r;
- //如果根最小,已经满足堆的条件,函数停止
- //否则
- if(largest != i)
- {
- //根与值最小的结点交互
- swap(A[i], A[largest]);
- //交换可能破坏子树的堆,重新调整子树
- Min_Heapify(largest);
- }
- }
-
- //建堆,时间是O(nlgn)
- void Heap::Build_Min_Heap()
- {
- heap_size = length;
- //从堆中最后一个元素开始,依次调整每个结点,使符合堆的性质
- for(int i = length / 2; i >= 0; i--)
- Min_Heapify(i);
- }
-
- //堆排序,时间是O(nlgn)
- void Heap::HeapSort(int A[])
- {
- //建立一个最小堆
- Build_Min_Heap();
- //每次将前i个元素构成最小堆
- for(int i = length-1; i >= 1; i--)
- {
- //将前i个元素中的最小值存入到A[i]中
- swap(A[0], A[i]);
- //堆的大小减一
- heap_size--;
- //只有堆顶的性质可能会被破坏
- Min_Heapify(0);
- }
- }
-
- //将元素i的关键字增加到key,要求key>=A[i]
- void Heap::Heap_Increase_Key(int i, int key)
- {
- if(key < A[i])
- {
- cout<<"new key is smaller than current key"<<endl;
- exit(0);
- }
- A[i] = key;
- //跟父比较,若A[PARENT(i)]<A[i],则交换
- //若运行到某个结点时A[PARENT(i)]>A[i],就跳出循环
- while(A[PARENT(i)] > 0 && A[PARENT(i)] > A[i])
- {
- swap(A[PARENT(i)], A[i]);
- i = PARENT(i);
- }
- }
-
- //把key插入到集合A中
- void Heap::Min_Heap_Insert(int key)
- {
- if(heap_size == N)
- {
- cout<<"heap is full"<<endl;
- exit(0);
- }
- heap_size++;length++;
- A[heap_size-1] = -0x7fffffff;
- Heap_Increase_Key(heap_size-1, key);
- }
- //返回A中最小关键字,时间O(1)
- int Heap::Heap_Minimum()
- {
- return A[0];
- }
- //去掉并返回A中最小关键字,时间O(lgn)
- int Heap::Heap_Extract_Min()
- {
- if(heap_size < 0)
- {
- cout<<"heap underflow"<<endl;
- exit(0);
- }
- //取出最小值
- int min = A[0];
- //将最后一个元素补到最小值的位置
- A[0] = A[heap_size-1];
- heap_size--;
- //重新调整根结点
- Min_Heapify(0);
- //返回最小值
- return min;
- }
- //删除堆中第i个元素
- void Heap::Heap_Delete(int i)
- {
- if(i > heap_size)
- {
- cout<<"there's no node i"<<endl;
- exit(0);
- }
- //把最后一个元素补到第i个元素的位置
- int key = A[heap_size-1];
- heap_size--;
- //如果新值比原A[i]小,则向上调整
- if(key < A[i])
- Heap_Increase_Key(i, key);
- else//否则,向下调整
- {
- A[i] = key;
- Min_Heapify(i);
- A[heap_size]=0;//这里把堆外的数置为0。保证已被删除的数不参与HeapSort函数运算。
- }
- }
-
- void Heap::Print()
- {
- int i;
- for(i = 0; i < heap_size; i++)
- {
- if(i > 0)cout<<',';
- else cout<<"==> A = {";
- cout<<A[i];
- }
- cout<<'}'<<endl;
- }
- void Heap::Print1()
- {
- int i;
- cout<<"==> A = {";
- for(i = 0; i < length; i++)
- {
- if (A[i]>0)
- {
- cout<<A[i]<<" ";
- }
- }
- cout<<'}'<<endl;
- }
- void main()
- {
- Heap a(13);
- a.A[0]=1;a.A[1]=9;a.A[2]=10;a.A[3]=2;a.A[4]=7;
- a.A[5]=5;a.A[6]=6;a.A[7]=4;a.A[8]=13;a.A[9]=3;
- a.A[10]=18;a.A[11]=11;a.A[12]=100;
- a.Build_Min_Heap();
- a.Print();
- a.Heap_Delete(2);
- a.Print();
- a.Heap_Extract_Min();
- a.Print();
- a.Heap_Increase_Key(8,15);
- a.Print();
- a.Min_Heap_Insert(10);
- a.Print();
- a.HeapSort(a.A);
- a.Print1();//由于排序后堆中已没有元素,所以要输出原数组中的数,
- }