钛节点

数据结构之最大堆和最小堆

发表@2018-09-13 09:15:22

更新@2023-01-21 22:47:40

这个堆并不是堆栈中那个堆，英文我们称之为Heap。堆就是完全二叉树，至于完全二叉树是什么鬼东西，有为青年可能还记得，其余青年可能忘的差不多了，然后自己默默上前面翻去。

堆分为两类，最大堆和最小堆。最大堆就是根结点的元素最大，然后以从上到下从左往右数据递减，最小堆呢就恰恰相反。这里值得注意的是堆的两个特性：

- 序号为x的结点，如果有左子树，那么左子树序号一定是2x；如果有右子树，那么右子树序号一定是2x+1
- 序号为x的结点，如果有父结点则其序号为floor( x / 2 )。floor表示不大于x的最大整数

像下面这货，就是典型的最小堆：

![](https://ti-node.com/static/upload/6413035881925443585)

最大堆自然就与最小堆相反：

![](https://ti-node.com/static/upload/6414848497299750913)

从图中可以观察到的是最大堆的任意一个结点的左右子树（只要存在）都比该结点要小，最小堆的任意一个结点的左右子树（只要存在）都比该结点要大。

那么话说回来，“堆”这玩意到底有啥用？

![](https://ti-node.com/static/upload/6414854167210229761)

其实，最大的作用就是堆排序！堆排序是一种不稳定排序，平均时间复杂度为( nlogn )，其中logn是用于构建堆，n用于排序。这种数据结构本身在我们需要top k这种排序的时候会优势比较明显，非常屌，值得掌握。

假如说我们有array( 50, 10, 90, 30, 70, 40, 80, 60, 20 )，然后需要将这个一维数组构建成最大堆，代码大概如下：

```php
<?php
class Base{
  public $fn = null;
	public $size = 0;
	public $element = [];
	public function __construct(){
		$this->element[ 0 ] = null;
		$this->fn = function( $data ){
			return $data;
		};
	}
}
class Max extends Base{
	public function __construct(){
		parent::__construct();
	}
	// arr 要调整的数组资源 
	// from 根节点的偏移量
	// to 子树的偏移量 
	// fn 函数
	public static function adjust( &$arr, $from, $to, $fn ){
		//$tempValue = $fn( $arr[ $from ] );
	  $rootValue = $arr[ $from ];	
		// parent 是根节点，parent * 2是左子树, ( parent * 2 ) + 1是右子树
    // 对于此处来说，收到的只有父节点而已，根据父节点来判断子节点而并不是直接将子节点当参数传输进来
    //echo 'from : '.$from.PHP_EOL;
		for( $parent = $from; $parent * 2 <= $to; $parent = $child ){
			$child = $parent * 2;
			if( $child < $to && $arr[ $child ] < $arr[ $child + 1 ] ){
		 	  $child++;
			}  	
		  //echo $parent.' : '.$child.PHP_EOL.PHP_EOL;
			// 如果根节点比子节点小，那么交换二者数据
			if( $rootValue < $arr[ $child ] ){
				$temp = $arr[ $parent ];
				$arr[ $parent ] = $arr[ $child ];
			  $arr[ $child ] = $temp;	
			} else {
				//echo "避免重复比较".PHP_EOL;
				break;
			}
		}
	}
	public static function array2max( array $arr ){
    $max = new Max();
    $max->size = count( $arr ); 
		array_unshift( $arr, null );
		//print_r( $arr );exit;
		// 开始循环数组
		for( $i = $max->size; $i > 0; $i-- ){
			// 这个循环就是用来 确定每个节点以及其父节点的
      $parentIndex = floor( $i / 2 ); 
			if( $parentIndex > 0 ){
			  //echo $parentIndex.PHP_EOL;
			  self::adjust( $arr, $parentIndex, $max->size, $max->fn );	
			}
		}
		$max->element = $arr;
		//print_r( $max->element );
		return $max;
	}
	public function delete(){
		$data = $this->element[ 1 ];
		$this->element[ 1 ] = $this->element[ $this->size ];
		self::adjust( $this->element, 1, $this->size-1, $this->fn );
		unset( $this->element[ $this->size ] );
		$this->size--;
		return $data;
	}
	public function insert( $data ){
		$this->size++;
		$this->element[ $this->size ] = $data;
		for( $i = $this->size; $i > 0; $i-- ){
			$parentIndex = floor( $i / 2 );
			if( $parentIndex > 0 ){
        self::adjust( $this->element, $parentIndex, $this->size, $this->fn );
			}
		}
	}
}
$max = Max::array2max( array( 50, 10, 90, 30, 70, 40, 80, 60, 20 ) );
print_r( $max->element );
$max->insert( 5 );
print_r( $max->element );
$max->delete();
print_r( $max->element );
```

实际上，有为青年可能已经研究到了，php的SPL中已经内置了Heap这种数据结构，我就贴个链接，你们感受一下：[点击这里](http://php.net/manual/en/spl.datastructures.php "点击这里")