当前位置:首页 > 开发 > 编程语言 > 编程 > 正文

最大堆 排序

发表于: 2012-04-15   作者:cshopping829   来源:转载   浏览:
摘要: 卸载最前面,下面的所有讨论都是基于二叉堆 一:什么是堆: 堆是一个数组结构,可以看着为一颗完全二叉树,把这颗完全二叉树按层从上到下,每层从左至右编序号,每个序号所对应的元素即为数组中该序号的元素;该树出最后一层以外每一层都排满,最后一层从左至右,先左孩子再右孩子排列,如果有父节点没有排满孩子(无孩子或无右孩子),只可能是右边的父节点未排满孩子。 因此该结构有如下结构: 如果节点i,则它
卸载最前面,下面的所有讨论都是基于二叉堆

一:什么是堆:
堆是一个数组结构,可以看着为一颗完全二叉树,把这颗完全二叉树按层从上到下,每层从左至右编序号,每个序号所对应的元素即为数组中该序号的元素;该树出最后一层以外每一层都排满,最后一层从左至右,先左孩子再右孩子排列,如果有父节点没有排满孩子(无孩子或无右孩子),只可能是右边的父节点未排满孩子。
因此该结构有如下结构:
如果节点i,则它的左孩子为2*I,右孩子为2*i+1;原因:节点i所对应的深度为h=log2(i);所以左孩子为2^log2(i)+2*(i-i/2)=2i;
二:堆排序过程
先构建堆—》把最后一个节点和第一个节点互换—》调整堆—》第一个节点与倒数第二个节点互换,依次进行:
三:代码
#include <stdio.h>
#include <math.h>
/*
假设i的左孩子与右孩子已经是一个最大堆,现在要把i放入到堆中,如果i比左右孩子都大直接放入,如果i比左孩子或者右孩子小,则与该孩子互换,交换以后再调整该孩子所在子树,一直调整到合适位置为止
*/
void heapify(int *pArray, int i, int iHeapSize)
{
int iLargest = i;
int iLeft = 2*i, iRight = 2*i+1;
int tmp;
if(iLeft < iHeapSize && *(pArray+i) < *(pArray+iLeft))
{
if(*(pArray+i) < *(pArray+iLeft))
{
iLargest = iLeft;
}
else
{
iLargest = i;
}
}
if(iRight < iHeapSize && *(pArray + iRight) > *(pArray + iLargest))
{
iLargest = iRight;
}

if(i != iLargest)
{
tmp =  *(pArray + iLargest);
*(pArray + iLargest) = *(pArray+i);
*(pArray+i) = tmp;
  heapify(pArray, iLargest, iHeapSize);
}
else
{
return;
}
}
/*
因为n/2+1~n都为叶子节点;
最后一层深度h = log2(n);倒数第二层最后一个节点为:2^(log2(n)-1)=n/2
*/
void buid_heap(int *pArray, int size)
{
for(int i = size/2-1; i >= 0;  i--)
{
heapify(pArray, i, size);
}
}

void heap_sort(int *pArray, int size)
{
int tmp;
int i;
buid_heap(pArray, size);
for(i = 0; i < size; ++i)
{
tmp = *(pArray);
*(pArray) = *(pArray + (size-1-i));
*(pArray + (size-1-i)) = tmp;
heapify(pArray, 0, size - i-1);
}
}

最大堆 排序

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号