算法系列-堆排序

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 条评论

tadalafil tadalafil · 2021年1月7日 下午9:18

I am also writing to make you know what a incredible encounter my friend’s girl experienced reading your site. She even learned many issues, not to mention what it’s like to have a wonderful giving mindset to have many people quite simply grasp chosen hard to do subject areas. You really exceeded our expectations. Many thanks for giving the insightful, healthy, educational and as well as easy thoughts on the topic to Jane.

cialis prices · 2021年1月8日 上午5:41

Thanks for your whole work on this website. My mum takes pleasure in setting aside time for research and it is simple to grasp why. We notice all relating to the powerful ways you provide very useful tips and tricks via your website and therefore strongly encourage response from visitors on this theme while our own simple princess is without a doubt understanding so much. Take pleasure in the rest of the year. Your performing a useful job.

order kamagra · 2021年1月8日 上午7:26

I needed to draft you one little bit of observation to finally thank you the moment again over the remarkable tactics you have shared on this page. This has been simply surprisingly open-handed with you to offer unhampered what most of us would’ve offered for sale for an ebook to help make some money on their own, precisely seeing that you might have tried it in case you desired. Those suggestions in addition worked to become good way to realize that some people have the identical keenness similar to my personal own to realize significantly more when it comes to this matter. I believe there are several more pleasant sessions up front for people who scan your site.

ARIPIPRAZOLE buy · 2021年1月8日 上午9:23

I am just writing to make you understand what a perfect experience my wife’s girl obtained using your webblog. She noticed so many pieces, which included what it is like to possess an excellent helping spirit to let other people with no trouble learn specific specialized things. You truly surpassed readers’ expected results. Thank you for providing these priceless, trusted, informative as well as fun tips about this topic to Lizeth.

cheap abilify · 2021年1月8日 上午10:00

I precisely desired to say thanks again. I’m not certain the things I could possibly have created without the type of secrets provided by you on such a question. It previously was a very frustrating issue in my opinion, however , observing the very specialised strategy you processed that made me to leap over gladness. I am just happy for this information and in addition hope that you know what a great job you are always getting into teaching people thru your web page. More than likely you have never got to know any of us.

发表评论

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