AfxStd.h
#pragma once
#ifndef AFXSTD_H
#define AFXSTD_H
#include
#include
#include
#endif // !AFXSTD_H
heap.h
#pragma once
#include"AfxStd.h"
#ifndef HEAP_H
#define HEAP_H
void HeapSort(int *arr, int length);
void MeakHeap(int *arr, int length);
void AdjustHeap_Down(int *arr, int start, int end);
void AdjustHeap_Up(int *arr, int start);
void swap(int *arr, int a, int b);
#endif // !HEAP_H
heap.cpp
#include"heap.h"
void MeakHeap(int *arr, int length)
{
if (arr == NULL)
{
return;
}
for (int i = (length -1)/2; i >= 0; i--)/*从第一个非叶子节点从下至上,从右至左调整结构*/
{
AdjustHeap_Down(arr, i, length - 1); /*调整函数中传入了数组,起始坐标,末尾坐标*/
}
}
void HeapSort(int *arr,int length) /*排序函数中是传入了数组的长度length*/
{
if (arr==NULL)
{
return;
}
for (int i=(length-1)/2;i>=0;i--)
{
/*从第一个非叶子节点从下至上,从右至左调整结构*/
AdjustHeap_Down(arr,i,length-1); /*调整函数中传入了数组,起始坐标,末尾坐标*/
}
/*调整堆结构,交换顶端元素与末端元素*/
for (int j=length-1;j>0;j--)
{
swap(arr,0,j);
AdjustHeap_Down(arr,0,j-1);
}
}
void swap(int *arr, int a, int b)
{
int temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
//AdjustHeap_Down,向下调整函数.作用是将数组转化为逻辑上的大堆,
//从而方便升序排序,如果要降序排序,该制堆函数将数组转化为小堆即可.
void AdjustHeap_Down(int *arr, int start, int end)
{
int i = start;
int j = 2 * i + 1;
int temp = arr[i];
while (j <= end)
{
if (j + 1 <= end && arr[j]
temp)
{
arr[i] = arr[j];
i = j;
j = 2 * i + 1;
}
else
{
break;
}
}
arr[i] = temp;
}
//Up,向下调整函数.作用是向上回溯使其符合小堆,也可稍作修使其符合大堆.
void AdjustHeap_Up(int *arr, int start)
{
int i = start;
int j = (start-1)/2;
int temp = arr[i];
while (j >=0)
{
if (arr[j]>temp)
{
arr[i] = arr[j];
i = j;
j = (j - 1) / 2;
}
else
{
break;
}
}
arr[i] = temp;
}
main.cpp
#include"PerioryQueue.h"
int main()
{
int arr[] = { 8,18,12,34,90,56,45,78 };
for (int i = 0; i<8; i++)
{
printf("%d\t", arr[i]);
}
HeapSort(arr, sizeof(arr) / sizeof(arr[0]));
printf("\n");
for (int i = 0; i<8; i++)
{
printf("%d\t", arr[i]);
}
return 0;
}