reconstruct_heap(array, swap, length);
}
} e）对单分支节点和满分支节点分别处理
int adjust_normal_position(int array[], int index)
{
int left = index << 1 ;
int right = left + 1;
int median = 0;
int swap = 0;
if(array[index] >= array[left]){
if(array[index] >= array[right]){
return -1;
}else{
swap = right;
}
}else{
if(array[index] >= array[right]){
swap = left;
}else{
swap = array[left] > array[right] left : right;
}
}
if(swap == left) {
median = array[index];
array[index] = array[left];
array[left] = median;
}else{
median = array[index];
array[index] = array[right];
array[right] = median;
}
return swap;
}
STATUS adjust_leaf_position(int array[], int index)
{
int median = 0;
if(array[index] > array[index << 1])
return TRUE;
median = array[index];
array[index] = array[index << 1];
array[index << 1] = median;
return FALSE;
}
int adjust_normal_position(int array[], int index)
{
int left = index << 1 ;
int right = left + 1;
int median = 0;
int swap = 0;
if(array[index] >= array[left]){
if(array[index] >= array[right]){
return -1;
}else{
swap = right;
}
}else{
if(array[index] >= array[right]){
swap = left;
}else{
swap = array[left] > array[right] left : right;
}
}
if(swap == left) {
median = array[index];
array[index] = array[left];
array[left] = median;
}else{
median = array[index];
array[index] = array[right];
array[right] = median;
}
return swap;
}
STATUS adjust_leaf_position(int array[], int index)
{
int median = 0;
if(array[index] > array[index << 1])
return TRUE;
median = array[index];
array[index] = array[index << 1];
array[index << 1] = median;
return FALSE;
}
f）堆排序算法介绍完毕，创建测试用例验证
static void test1()
{
int array[] = {1};
heap_sort(array, sizeof(array)/sizeof(int));
}
static void test2()
{
int array[] = {2, 1};
heap_sort(array, sizeof(array)/sizeof(int));
assert(1 == array[0]);
assert(2 == array[1]);
}
static void test3()
{
int array[] = {3, 2, 1};
heap_sort(array, sizeof(array)/sizeof(int));
assert(1 == array[0]);
assert(2 == array[1]);
assert(3 == array[2]);
}
static void test4()
{
int array[] = {2, 3, 1};
heap_sort(array, sizeof(array)/sizeof(int));
assert(1 == array[0]);
assert(2 == array[1]);
assert(3 == array[2]);
}
static void test5()
{
int array[] = {5,3, 4, 1};
heap_sort(array, sizeof(array)/sizeof(int));
assert(1 == array[0]);
assert(3 == array[1]);
assert(4 == array[2]);
assert(5 == array[3]);
}
static void test6()
{
int array[] = {2, 3,6, 8, 7};
heap_sort(array, sizeof(array)/sizeof(int));
assert(2 == array[0]);
assert(3 == array[1]);
assert(6 == array[2]