算法系列-堆排序

phpman.song@gmail.com发布

定义

堆排序指利用堆这种数据结构所设计的一种排序算法

  1. 大顶堆:每个节点的值都大于或等于其子节点的值,在堆排序算法中用于升序排列;
  2. 小顶堆:每个节点的值都小于或等于其子节点的值,在堆排序算法中用于降序排列;

原理

  1. 创建一个堆H[0,1,…,n-1,n]
  2. 把堆首(最大值)和堆尾互换
  3. 把堆的尺寸缩小1,并调用shif_down(0),目的时把新的数组顶端数据调整到相应位置
  4. 重复步骤2,直到堆的尺寸为1

PHP实现

PHP沙盒环境

function buildMaxHeap(&$arr)
{
    global $len;
    for ($i = floor($len/2); $i >= 0; $i--) {
        heapify($arr, $i);
    }
}

function heapify(&$arr, $i)
{
    global $len;
    $left = 2 * $i + 1;
    $right = 2 * $i + 2;
    $largest = $i;

    if ($left < $len && $arr[$left] > $arr[$largest]) {
        $largest = $left;
    }

    if ($right < $len && $arr[$right] > $arr[$largest]) {
        $largest = $right;
    }

    if ($largest != $i) {
        swap($arr, $i, $largest);
        heapify($arr, $largest);
    }
}

function swap(&$arr, $i, $j)
{
    $temp = $arr[$i];
    $arr[$i] = $arr[$j];
    $arr[$j] = $temp;
}

function heap_sort($arr) {
    global $len;
    $len = count($arr);
    buildMaxHeap($arr);
    for ($i = count($arr) - 1; $i > 0; $i--) {
        swap($arr, 0, $i);
        $len--;
        heapify($arr, 0);
    }
    return $arr;
}

//例子
$numbers = [1,3,4,22,88,33,31,42];
print_r(heap_sort($numbers));
分类: 算法

16 条评论

escitalopram online · 2021年1月9日 上午12:03

I am only writing to make you understand what a really good experience my wife’s princess obtained viewing your webblog. She noticed some things, which included what it is like to possess an ideal teaching spirit to make others without difficulty learn about specific tortuous things. You undoubtedly surpassed readers’ expected results. Thanks for rendering those productive, trusted, informative as well as unique tips on your topic to Mary.

paxil price · 2021年1月9日 上午7:55

I am commenting to let you know of the fine encounter my friend’s daughter found reading your site. She figured out many issues, not to mention what it’s like to have a wonderful giving mindset to have men and women quite simply have an understanding of selected hard to do subject areas. You really exceeded our expectations. Many thanks for giving the insightful, safe, explanatory and as well as easy thoughts on the topic to Jane.

nortriptyline cheap · 2021年1月9日 上午9:44

I am glad for writing to make you know what a notable encounter my wife’s girl had studying your web site. She mastered several pieces, which include what it’s like to possess an awesome helping nature to let other individuals with ease know precisely some problematic subject matter. You truly exceeded people’s expectations. Thank you for producing these practical, trusted, informative and in addition fun tips about this topic to Kate.

quetiapine no rx · 2021年1月9日 下午8:47

I’m commenting to let you be aware of of the beneficial discovery my child developed browsing the blog. She came to find a lot of details, including how it is like to have a great coaching character to get certain people completely comprehend a number of complex issues. You actually did more than her desires. I appreciate you for coming up with such effective, dependable, edifying and cool guidance on that topic to Ethel.

venlafaxine buy · 2021年1月9日 下午8:49

Thank you for your entire labor on this web site. My mom take interest in managing investigations and it is obvious why. My partner and i learn all regarding the lively tactic you produce simple things through your web site and in addition invigorate response from the others on the situation then our favorite princess is truly studying a whole lot. Take advantage of the rest of the year. You have been doing a superb job.

发表评论

邮箱地址不会被公开。 必填项已用*标注