算法导论第六章堆排序 6.5-8

题目描述

6.5-8HEAP-DELETE（A，i）操作能过将结点i从堆A中删除。对于一个包括n个元素的堆，请设计一个能够在O(lg n)时间内完成的HEAP-DELETE操作。

思路：把堆中的最后一个元素A[A.heap-size]放到结点i上，然后A.heap-size - 1.

分三种情况：

（1） A[A.heap-size] = A[i] 无需调整，时间复杂度为O（1）.

（2） A[A.heap-size] > A[i] 调用HEAP-INCREASE-KEY（A， i， key）时间复杂度为O（lg n）.

（3） A[A.heap-size] < A[i] 调用MAX-HEAPIEY（A， i），维护堆的性质，时间复杂度为O（lg n）.

 1 class TestController extends Controller{
 2     /**
 3      * 维护堆的性质. 
 4      * 
 5      * @param  Array $a 
 6      * @param  int $i 
 7      * @param  int $heapsize
 8      * @access public
 9      * @return void
10      */
11     public function MaxHeapify($a, $i, $heapsize){
12         $largest = 0;
13         $left = 2*$i;
14         $right = (2*$i)+1;
15         $temp = 0;
16         if ($left <= $heapsize && $a[$left] > $a[$i]) {
17             $largest = $left;
18         }else {
19             $largest = $i;
20         }
21         if ($right <= $heapsize && $a[$right] > $a[$largest]) {
22             $largest = $right;
23         }
24         if ($largest != $i) {
25             $temp = $a[$i];
26             $a[$i] = $a[$largest];
27             $largest = $temp;
28             $this::MaxHeapify($a, $largest, $heapsize);
29         }
30     }
31     /**
32      * 增加某个键的值. 
33      * 
34      * @param  Array $a 
35      * @param  int $i 
36      * @param  int $heapsize
37      * @access public
38      * @return void
39      */
40     public function HeapIncreaseKey($a, $i, $key,$heapsize){
41         $parent = floor($i/2);
42         $temp = 0;
43         if ($key < $a[$i]) {
44             return "have a problem";
45         }
46         $a[$i] = $key;
47         while ($i <= 1 && $a[$parent] < $a[$i]) {
48             $temp = $a[$parent];
49             $a[$parent] = $a[$i];
50             $a[$i] = $temp;
51         }
52     }
53     /**
54      * 删除键. 
55      * 
56      * @param  Array $a 
57      * @param  int $i 
58      * @param  int $heapsize
59      * @access public
60      * @return void
61      */
62     public function HeapDelete($a, $i, $heapsize){
63         $temp = $a[$heapsize];
64         if ($heapsize < 1) {
65             return "have a problem";
66         }
67         if ($a[$heapsize] == $a[$i]) {
68             $heapsize = $heapsize - 1;
69         }elseif ($a[$heapsize] > $a[$i]) {
70             $this::HeapIncreaseKey($a, $i, $a[$heapsize], $heapsize);
71         }elseif ($a[$heapsize] < $a[$i]) {
72             $this::MaxHeapify($a, $i, $heapsize);
73         }
74         $heapsize = $heapsize - 1;
75         return $a;
76     }
77 }

算法导论 第六章 堆排序 6.5-8

算法导论第六章堆排序 6.5-8