微信号:phpgod

介绍:本公众号对PHP开发技术进行全面透析,所含内容适合各个阶段的PHP developer阅读和收藏,既然关注了就一定会有收获.

PHP实现堆、堆排序以及索引堆

2016-12-23 22:47 猿哥

本文转载自:http://sunms.codefly.top/2016/12/20/php实现堆堆排序以及索引堆/

堆是一种非常常用的数据结构,常常用来实现优先队列。下面来说一下,堆的一些特性。

堆(二叉堆)的成立条件如下:具有n个元素的序列:{k1,k2,ki,…,kn} ,(ki <= k2i,ki <= k2i+1) 或者 (ki >= k2i,ki >= k2i+1), (i = 1,2,3,4…n/2)。满足第一个条件的我们称之为最小堆,满足第二个条件的我们称之为最大堆。其实堆(二叉堆)我们可以用完全二叉树进行描述(堆本身我们可以理解成完全二叉树,不理解完全二叉树的可以先看一下),每一个父节点对应最多两个子节点,且父节点的值都是大于或者两个子节点的值的。下面的图片就是用完全二叉树描述的最大堆以及最小堆,大家可以看一下。

在实现堆这种数据结构的时候,通常都会采用链表或者数组的形式,这里我们以数组的形式来实现一个堆,事实上利用数组来实现堆是一种经典的堆的实现方式。

利用数组实现堆的原理:假设我们将以数组中index为1的位置开始来存放堆中的元素,假设index为n的位置上存在一个元素,那么它的子元素在数组中存放位置就是index = 2*n 以及index = 2*n +1 。这里需要注意的是我们是以index为1的位置开始存放元素的,并不是以index=0来存放的,如果以index=0来存放,那么它的子元素在数组中存放的位置就是index = 2*n + 1以及index = 2*n + 2。

下面我们就用php初始化一个堆,先来看一下具体的思路。假设现在我们向length=n的数组堆中添加一个元素,那么数组堆中的前n个元素继续保持堆的特性,新添加的元素以后,length=n+1的数组就不再满足堆的特性了,所以我们需要对最后一个元素,也就是新添加的元素进行位置的调整。根据新添加的元素在数组中的索引,来计算出其父节点的索引,然后对新元素和父节点元素进行大小的比较,如果新添加的元素大于父节点元素,就需要进行数据的交换,如果新添加的元素小于等于父节点元素,就不需要进行比较了,因为新添加的元素正在其合适的位置之上。数据交换完成以后,可能还是破坏了堆的特性,需要继续进行刚才的步骤,直到需要比较的节点的索引小于1为止。

下面来看代码:

//初始化数组堆$heap_arr = [];//定义向堆中添加元素的方法function heap_add(&$heap_arr,$value){
    $heap_arr[] = $value;
    $count_arr = count($heap_arr);    //进行堆的调整
    if($count_arr > 1){
        $n = $count_arr-1;        while($n >= 2){            //查找父节点id
            $parent_n = floor($n/2);            //如果子节点的value大于其父节点的value,就进行交换
            if($heap_arr[$n]>$heap_arr[$parent_n]){                //进行数据的交换
                $temp = $heap_arr[$n];
                $heap_arr[$n] = $heap_arr[$parent_n];
                $heap_arr[$parent_n] = $temp;
                $n = $parent_n;
            }else{                //如果子节点的value小于等于父节点的value,直接退出
                break;
            }
        }
    }
}
heap_add($heap_arr,0);
heap_add($heap_arr,9);
heap_add($heap_arr,6);
heap_add($heap_arr,10);
heap_add($heap_arr,4);
heap_add($heap_arr,1);
heap_add($heap_arr,10);
heap_add($heap_arr,11);
heap_add($heap_arr,5);
print_r($heap_arr);

上面的代码我们就实现了向数组堆中添加元素,并且保证了数组$heap_arr一直保持堆的性质。下面,我们就来看一下如何获取上面数组堆中的数据。先看一下思路:我们上面实现的堆其实是一个最大堆,也就是说数组中索引为1的位置存放着整个数组中最大的元素(最小堆实现方式一样)。当我们获取出数组堆中最大值以后,当前的数组就不再满足树形的结构了,也就不再满足堆的特性了。但是因为堆本身就是一个完全二叉树,那么我们可以将数组中的最后一个元素放到索引为1的位置上去,这样的话,数组继续保持这树形结构,但仍然可能不是堆的特性。为了保证数组继续保持堆的特性,就需要调整当前的数组。调整的步骤,回去当前节点(索引为1的节点)的子节点,获取子节点中的最大值,然后对比当前节点以及子节点中的最大值进行比较,如果当前节点小于子节点中的最大值,就进行交换,依此类推,直到需要比较的节点索引大于数组最大的索引值为止。

具体看代码:

//定义获取最大值元素的函数function heap_del(&$heap_arr){
    $count_arr = count($heap_arr);    if($count_arr<=1){        return "";
    }    if($count_arr==2){        return $heap_arr[1];
    }    //如果数组的长度大于2个的时候
    $last_value = $heap_arr[$count_arr-1];    //删除最后一个元素
    unset($heap_arr[$count_arr-1]);    //将数组中最后一个元素放到数组的第二个位置上去
    $heap_arr[1] = $last_value;    //进行下沉操作
    $n = 1;
    $max_node = $count_arr-2;    while($n<$max_node){
        $left_son_node = $n*2;
        $right_son_node = $n*2+1;        if($left_son_node>$max_node && $right_son_node>$max_node){            break;
        }        if($left_son_node<=$max_node && $right_son_node>$max_node){
            $swap_node = $left_son_node;
        }        if($left_son_node>$max_node && $right_son_node<=$max_node){
            $swap_node = $right_son_node;
        }        if($left_son_node<=$max_node && $right_son_node<=$max_node){            //进行比较,取出较大值
            if($heap_arr[$left_son_node]>=$heap_arr[$right_son_node]){
                $swap_node = $left_son_node;
            }else{
                $swap_node = $right_son_node;
            }
        }        //进行数据的交换
        if($heap_arr[$swap_node]>$heap_arr[$n]){
            $temp = $heap_arr[$swap_node];
            $heap_arr[$swap_node] = $heap_arr[$n];
            $heap_arr[$n] = $temp;
            $n = $swap_node;
        }else{            break;
        }
    }
}
heap_del($heap_arr);
print_r($heap_arr);

上面我们就实现了获取最大值的方法。那么如何进行堆排序那?其实上面的获取最大值方式就是堆排序的实现方式,依次获取当前数组堆中的最大值,并且保持堆的性质。堆排序也是非常重要的一种排序方式,其时间复杂度是O(NlogN),并且是一种稳定的排序方式。但是上面的堆排序的代码我们可以继续优化,以提高排序的性能。排序的思路如下:根据上面的介绍,传递进来的数组是满足最大完全二叉树的结构的,但是整体不一定满足堆的特性。并且这个完全二叉树中所有的叶子节点都是满足堆的特性的,但是非叶子节点及其子节点就不一定满足堆的特性了。那么我们就可以找到完全二叉树中最后一个非叶子节点,然后对这个节点进行”下沉”操作,使其及其子节点保证满足堆的特点,然后依次处理所有的非叶子节点,直到让整个数组都满足堆的特性。

下面来看代码:

//随便定义一个无序的数组$test_array = [0,1,2,3,4,5,6,7,8,2];//定义一个堆化函数function heapify(&$array){
    $count = count($array);    //获取最后一个非叶子节点的index
    $last_index = floor(($count-1-1)/2);    while($last_index>=0){
        heap_down($array,$last_index);
        $last_index-=1;
    }
}//对数组进行堆化处理heapify($test_array);echo "<pre/>";
print_r($test_array);

使用上面的定义好的heapify()堆化函数继续堆排序的时间复杂度为O(N),在排序速度上要比之前的堆排序要快很多。

好了,说完了堆排序,我们继续说索引堆。什么是索引堆那?所谓索引堆,简单地说,就是在堆里头存放的不是数据,而是数据所在数组的索引,也就是下标(本文中索引和下标是一个意思,互相换用),根据数据的某种优先级来调整各个元素对应的下标在堆中的位置。

为什么需要使用索引堆那?这是因为堆这种数据结构存在两个缺点。(1):在堆中的元素体积非常大的情况下,经常性的移动元素是低效的。(2):如果在堆的使用过程中,堆中的元素的值要改变,则普通堆对此无能为力。如果是单纯的修改元素的值,那么数组就不再满足堆的特性了。

我们先来看一下下面的索引堆实例:

index 1 2 3 4 5 6 7 8 9 10
heap 10 9 7 8 5 6 3 1 4 2
data 15 17 19 13 22 16 28 30 41 62

数组堆中存放的是其对应的元素在data数组中的索引。如果我们在data数组中添加了一个元素,那么我们就将新添加的元素在data数组中的索引添加到heap数组的尾部。那么heap数组因为新添加了元素,就需要进行堆的调整。和以前实现代码的思路一样,将新添加到heap数组中的元素与其父节点进行比较(实际是那heap中的元素作为索引所对应的data数组中元素进行比较的,这点比较绕),如果子节点对应的元素大于父节点对应的数据就进行交换。获取索引堆中的最大值等操作和上面的思路是一样的,这里就不在赘述了。

这里主要说一下,更改data数组中数据的操作。首先,获取需要修改的data数组中的数据所对应的索引值以及需要修改成值,然后修改data中的数据。根据data数组中所对应的索引,去heap数组中查找值为data中索引的索引(节点,这里有点绕),然后对这个节点进行上浮以及下沉的操作,保证数组满足堆的特性。

下面我们直接看实现索引堆的代码:

//索引堆的实现//数组堆,用来存放index$heap_array = [];//元素数组$array = [];//添加元素到队列中function init($item,&$heap_array,&$array){    //添加元素到数组中
    $array[] = $item;    //获取添加的元素所对应的index
    $last_index = count($array)-1;    //数组堆
    $heap_array[] = $last_index;    //进行堆化处理,维持堆的性质
    heap_up($heap_array,$array,$last_index);
}//获取最大堆中的堆顶元素(最大元素)function get_max(&$heap_array,&$array){
    $count_heap_array = count($heap_array);    if($count_heap_array<1){        return;
    }    //获取最大值所对应的索引
    $index = $heap_array[0];    //获取最大值
    $return_value = $array[$index];    //获取堆中最后一个元素
    $last_index = $heap_array[count($heap_array)-1];
    $heap_array[0] = $last_index;    unset($heap_array[count($heap_array)-1]);    //进行堆的下沉操作
    heap_down($heap_array,$array);    //返回最大值
    return $return_value;
}//修改数组中的内容function change(&$heap_array,&$array,$index,$value){    if($index<0 || $index>(count($array)-1)){        return false;
    }    //修改$array中的数据
    $array[$index] = $value;    //在$heap_array查找$index的位置
    for($i=0;$i<count($heap_array);$i++){        if($index = $heap_array[$i]){            //进行调整
            heap_down($heap_array,$array,$i);
            heap_up($heap_array,$array,$i);
        }
    }
}//堆的下沉操作function heap_down(&$heap_array,&$array,$index=0){    //$index = 0;
    $last_index = count($heap_array)-1;    while($index<$last_index){
        $left_index = 2*$index + 1;
        $right_index = 2*$index + 2;        //比较left_index与right_index所对应的值
        if($left_index>$last_index){            break;
        }        if($left_index<=$last_index && $right_index<=$last_index){            if($array[$heap_array[$left_index]]<$array[$heap_array[$right_index]]){
                $swap_index = $right_index;
            }else{
                $swap_index = $left_index;
            }
        }        if($left_index<=$last_index && $right_index>$last_index){
            $swap_index = $left_index;
        }        //进行数据的交换
        if ($array[$heap_array[$swap_index]] > $array[$heap_array[$index]]) {
            $temp = $heap_array[$swap_index];
            $heap_array[$swap_index] = $heap_array[$index];
            $heap_array[$index] = $temp;
            $index = $swap_index;
        } else {            break;
        }
    }
}//堆的上浮操作function heap_up(&$heap_array,&$array,$index){    while($index>0){        //获取当前节点的父节点
        $parent_index = floor(($index-1)/2);        //将当前节点与父节点所对应的数据进行比较
        if($array[$heap_array[$index]]>$array[$heap_array[$parent_index]]){            //进行数据的交换
            $temp = $heap_array[$index];
            $heap_array[$index] = $heap_array[$parent_index];
            $heap_array[$parent_index] = $temp;
            $index = $parent_index;
        }else{            break;
        }
    }
}//添加元素的操作init(1,$heap_array,$array);
init(0,$heap_array,$array);
init(3,$heap_array,$array);
init(4,$heap_array,$array);
init(5,$heap_array,$array);
init(6,$heap_array,$array);
init(2,$heap_array,$array);
init(0,$heap_array,$array);
init(1,$heap_array,$array);echo "<pre/>";echo "heap_array<br/>";
print_r($heap_array);echo "array<br/>";
print_r($array);
change($heap_array,$array,0,100);echo "修改数据<br/>";echo "heap_array<br/>";
print_r($heap_array);echo "array<br/>";
print_r($array);echo "<br/>";echo get_max($heap_array,$array);

关注微信公众号:PHP技术大全

PHPer升级为大神并不难!


 
PHP技术大全 更多文章 谈谈PHP的Reload操作 亮灯问题-2016滴滴研发笔试题 51CTO专题文章之DDoS攻击原理及防护方法论 5道谷歌面试题(有答案) 一次PHP脚本执行卡住的问题排查记录
猜您喜欢 焕然一新的DaoCloud 英语流利说基础数据平台 CSharp拾遗之接口、索引器的本质(学习笔记) 老司机教你远端撸镜像 数据结构和算法(三):红黑二叉树