【数据结构】堆(C++)

//堆的结构
typedef struct _Heap
{
	int* arr;
	int size;
	int capacity;
}Heap;


void buildHeap(Heap& hp);
void adjustDown(Heap& hp, int index);
bool insertHeap(Heap& hp, int val);

//堆的初始化
bool initHeap(Heap& hp, int* orginal, int size)
{
	int capacity = DEFAULT_CAPCITY > size ? DEFAULT_CAPCITY : size;
	hp.arr = new int[capacity];
	if (!hp.arr)
	{
		return false;
	}
	hp.capacity = capacity;
	hp.size = 0;

	//如果存在原始数据则构建堆
	if (size > 0)
	{
		//方式1：直接全部拿过来
		/*_memccpy(hp.arr, orginal, size, size * sizeof(int));
		hp.size = size;
		buildHeap(hp);*/

		//方式2：一个一个插入 ，插一次排一次
		for (int i = 0; i < size; i++)
		{
			insertHeap(hp, orginal[i]);
		}
	}
	return true;
}

//构建堆
void buildHeap(Heap& hp)
{
	for (int i = ((hp.size - 1)-1) / 2; i >= 0; i--)
	{
		adjustDown(hp, i);
	}
}

//向下调整——根据已经有的数据内容进行调整
void adjustDown(Heap& hp,int index)
{
	int cur = hp.arr[index];//当前父节点的值
	int parent = 0;//索引
	int child = 0;
	//调整是一个循环的过程，整个向下
	//能够进入循环的条件，它得有左子结点。
	for (parent = index; (parent * 2 + 1) < hp.size; parent = child)//for循环的最后一个参数，定位新的父结点索引
	{
		//从最后一个父结点开始，父结点肯定有左孩子
		child = parent * 2 + 1;
		 
		//取两个子结点中较大的一个
		if (((child + 1) < hp.size) && hp.arr[child] < hp.arr[child + 1])
		{
			child++;//如果右边的孩子大，那就拿到右边孩子的下标
		}
	
		//将子结点与父结点进行对比
		if (cur >= hp.arr[child])
		{
			break;//如果在高层，此时父结点大于子结点就break,因为是从底层上来的，比父结点都大
		}
		else
		{
			hp.arr[parent] = hp.arr[child];
			hp.arr[child] = cur;
		}
	}
}

//向上调整——对新插入的元素进行调整
void adjustUp(Heap& hp, int index)
{
	while (index > 0)
	{
		int temp = hp.arr[index];//要插入的结点
		int parent = (index - 1) / 2;
		if (temp > hp.arr[parent])
		{
			hp.arr[index] = hp.arr[parent];
			hp.arr[parent] = temp;
			index = parent;
		}
		else
		{
			//如果已经小于等于父亲的值了
			break; 
		}
	}
}

//加入新的元素
bool insertHeap(Heap& hp, int val)
{
	if (hp.size == hp.capacity)
	{
		return false;
	}
	int index = hp.size;//保存新加入元素的位置，因为size要++
	hp.arr[hp.size++] = val;
	adjustUp(hp,index);
	return true;
}

//打印输出堆中元素
void printHeap(Heap& hp)
{
	int num = hp.size;
	int front = 0;
	int back = 1;
	int row = 1;
	while (num)
	{
		for (int j = front; j < back; j++)
		{
			cout << hp.arr[j] << " ";
		}
		cout << endl;
		num -= row;//输出完本行还剩的元素个数
		//如果减去本行输出的个数小于0
		if (num <= 0)
		{
			break;
		}
		row *= 2;//下一行要输出的元素个数

		front = back;//定位下一行的起点

		if (num - row <= 0)//如果当前的元素个数不够输出下一行的，直接定位下一行的back位置
		{
			back = hp.size;
		}
		else// 够则——手动定位结尾位置
		{
			back += row;
		}
	}

}

//弹出堆顶元素
void popTop(Heap& hp)
{
	hp.arr[0] = hp.arr[hp.size - 1];
	hp.size--;
	buildHeap(hp);

}

#include<iostream>
using namespace std;

void adjustDown(int* ary, int index, int tatal)
{
	int cur = ary[index];
	int parent = 0;
	int child = 0;

	for (parent = index; (parent * 2 + 1) < tatal; parent = child)
	{
		child = parent * 2 + 1;
		if (((child + 1) < tatal) && (ary[child] < ary[child + 1]))
		{
			child++;
		}
		
		if (cur >= ary[child])
		{
			break;
		}
		else
		{
			ary[parent] = ary[child];
			ary[child] = cur;
		}
	}
}


void HeapSort(int* ary,int size)
{
	int tempS = size;
    //先用这个数组键一个堆
	for (int i = (size - 1 - 1) / 2; i >= 0; i--)
	{
		adjustDown(ary, i, tempS);
	}
    //必须要先建好一个堆
    //因为这样将堆顶元素和堆尾元素交换之后，除了堆顶新换过来了元素，“仍”是一个最大(小)堆，因为比较就要和父节点比。
    
	int front = 0;
	int back = tempS - 1;
	for (;back > 0; back--)
	{ 
		int tempChange = ary[front];
		ary[front] = ary[back];
		ary[back] = tempChange;
		adjustDown(ary, front, --tempS);
	}	
}

int main(void)
{
	int arraY[] = {3,1,2,4,56,7,89,99};
	int size = sizeof(arraY) / sizeof(arraY[0]);

	HeapSort(arraY, size);

	for (int i = 0; i < size; i++)
	{
		cout << arraY[i] << " ";
	}
	return 0;
}