STL经典算法集锦<二>之堆算法

堆算法主要包括建立最大堆和堆排序算法。所使用建堆的数组将以0开始存储数据。

下面将以两种方法建堆：自底向上的建堆（STL和算法导论中使用到的）、自顶向下建堆（即插入建堆的方法）

公共操作：

int parent(int i)
{
    return (int)((i-1)/2);
}
 
int left(int i)
{
    return 2 * i+1;
}
 
int right(int i)
{
    return (2 * i + 2);
}

版本一：自底向上

void heapShiftDown(int heap[], int i, int heap_size)
{
    int l = left(i);
    int r = right(i);
    int largest=i;
	//找出左右字节点与父节点中的最大者
    if(l < heap_size && heap[l] > heap[largest])
        largest = l;
    if(r < heap_size && heap[r] > heap[largest])
        largest = r;
	//若最大者不为父节点，则需交换数据，并持续向下滚动至满足最大堆特性
    if(largest != i)
    {
		swap(heap[largest],heap[i]);
        heapShiftDown(heap, largest, heap_size);
    }
}
 //自底向上的开始建堆，即从堆的倒数第二层开始
void buildHeap(int heap[],int heapSize)
{
    for(int i = (heapSize-1)/2; i >= 0; i--)
    {
        heapShiftDown(heap, i, heapSize );
    }
}
 

版本二：自顶向下的建堆

//i为新插入节点的位置
void heapShiftUp(int heap[], int i)
{
    int p=parent(i);
	//判断插入新节点后是否满足最大堆
	//否则交换数据并持续向上滚动
    if( heap[i] > heap[p])
	{		
			swap(heap[i],heap[p]);
			if(p != 0)
					heapShiftUp(heap,p);
	}
}
 
void buildHeap(int heap[],int heapSize)
{
	//自第二层开始建堆
    for(int i = 1; i < heapSize; i++)
    {
        heapShiftUp(heap, i);
    }
}

堆排序：

void heapSort(int heap[], int heapSize )
{
    buildHeap(heap,heapSize);
    for(int i = heapSize- 1; i > 0; i--)
    {
		swap(heap[0],heap[i]);
                heapShiftDown(heap, 0, i);
    }
}

测试代码：

int main()
{
		int len=20;
		int array[len];
		srand(time(0));
		for(int i=0;i<len;i++)
				array[i]=rand()%200;
		heapSort(array,len);
		for(int i=0;i<len;i++)
				cout<<array[i]<<"	";
		return 0;
}

单次运行结果：
自底向上：

自顶向下：