算法系列-堆排序

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

sprzedam samochód · 2021年1月5日 上午7:13

Świetny post. Bardzo ciekawie opisany artykuł. Jak możesz sprawdź stronę o samochodach u mnie! Do zobaczenia!

peugeot 307 replacement key · 2021年1月5日 上午9:50

Very interesting details you have noted, appreciate it for putting up.

auto locksmith vauxhall · 2021年1月6日 上午12:07

I really like looking at and I believe this website got some really useful stuff on it!

samochody · 2021年1月6日 上午1:08

Bardzo lubię patrzeć i uważam, że ta strona zawiera naprawdę przydatne rzeczy!

cbd oil · 2021年1月7日 上午9:57

I needed to draft you one little observation so as to say thank you as before for these gorgeous guidelines you’ve contributed at this time. It’s extremely generous of people like you in giving extensively all a few people could have distributed as an e-book in order to make some bucks for their own end, certainly considering that you could have done it if you considered necessary. The creative ideas additionally acted as the easy way to be certain that most people have a similar dream just as mine to find out a little more in regard to this condition. I’m certain there are lots of more enjoyable moments ahead for folks who discover your blog.

发表评论

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