堆(Heap)

1.优先队列

特殊的队列，出队列的顺序按照优先级顺序。

1.1实现方法

2.优先队列的完全二叉树表示即是堆

2.1 堆的特点：

所有根结点是最大值或最小值

最大堆：从上之下每个结点从大到小（最小堆同理）

3. 堆的插入和删除(小顶堆)

3.1堆的插入

先插入到最后，然后调整堆。
调整堆的操作为判断父节点是否比 value 大 ，如果比 value 将此父节点往下调，最后找到 value 插入的位置。

void HEAP::push(int value) {  //最小堆插入
    int i = ++cur_size;
    for (; data[i / 2] > value; i /= 2)
    {
        data[i] = data[i / 2];
    }
    data[i] = value;
}

3.2堆的删除

堆的删除直接删除堆顶，但是删完后得做调整。
删除后将最后一个元素放到堆顶，然后判断孩子与此时堆顶的关系，如果孩子更小将孩子放入父节点，依次循环。
判断孩子节点时 需要判断左右孩子的大小。
循环终止条件为找到堆顶位置或无孩子节点

void HEAP::pop() {
   int temp = data[cur_size--];
   int Child = 0;
   int Par = 0;
   data[1] = temp;
   for (Par = 1; Par * 2 <= cur_size; Par = Child)
   {
       Child = Par * 2;
       if (data[Par * 2] > data[Par * 2 + 1])
       {
           Child = Child++;
       }
       if (data[Child] >= temp)
       {
           break;
       }
       else
       {
           data[Par] = data[Child];
       }
   }
   data[Par] = temp;
}

4. 给数组构建大根堆

首先先建立大根堆数组

void BuildMaxHeap(int A[],int len)
{
	for(int i = len/2;i > 0;i--)
	{
		HeadAdjust(A,i,len);
	}
}

void HeadAdjust(int A[],int k,int len) 
{
	int temp = A[k];
	int i = k*2;
	for(;i <= len;i *= 2)  // i 一直指向大的子孩子，和根节点 k 相比是否需要替换，如果能替换需要继续下沉比较
	{
		if( i+1 <= len && A[i+1] > A[i])
			 i++;
		if(A[k] > A[i]) break;
		else
		{
			A[k] = A[i];
			k = i;
		}
	}
	A[k] = temp;
}

建立后 heap.top 是最大元素，此时与末尾元素交换再调整即可排序。

void Heapsort(int A[],int len)
{
	BuildHeap(A,len);
	for(int i = 1;i < len;i++)
	{
		
	}
}