JIYIK CN >

Like other sorting algorithms, let's first look at the definition of heap sort.

Heapsort : refers to a sorting algorithm designed using the heap data structure. A heap is a structure that approximates a complete binary tree and satisfies the properties of a heap: the key value or index of a child node is always smaller than (or larger than) its parent node.

From the last sentence of the above definition, we can also derive two concepts - the big top heap and the small top heap.

The so-called max-heap is that the key value or index of a child node is always smaller than its parent node. The sequence obtained by the max-heap is increasing.

The so-called mini-heap is that the key value or index of the child node is always greater than its parent node. The sequence obtained by the mini-heap is decreasing.

In fact, the construction principles of the big top heap and the small top heap are the same. In this article, we only introduce one of them, and we will take the big top heap as an example.

Let's take a look at the idea of ​​heap sort.

By taking advantage of the fact that the top of the small heap records the largest keyword, it is easy to select the largest record from the unordered area each time. The basic idea is (big heap): 1) The initial sequence of keywords to be sorted (R1, R2….Rn) is constructed into a big heap, which is the initial unordered area; 2) The top element R[1] of the heap is exchanged with the last element R[n], and a new unordered area (R1, R2,…Rn-1) and a new ordered area (Rn) are obtained, and R[1,2…n- 1]<=R[n] are satisfied; 3) Since the new top R[1] after the exchange may violate the properties of the heap, it is necessary to adjust the current unordered area (R1, R2,…Rn-1) to a new heap, and then exchange R[1] with the last element of the unordered area again to obtain a new unordered area (R1, R2….Rn-2) and a new ordered area (Rn-1, Rn). Repeat this process until the number of elements in the ordered area is n-1, and the entire sorting process is completed. The operation process is as follows: 1) Initialize the heap: construct R[1..n] as a heap; 2) Exchange the top element R[1] of the current unordered area with the last record in the interval, and then adjust the new unordered area to a new heap. Therefore, for heap sorting, the two most important operations are constructing the initial heap and adjusting the heap. In fact, constructing the initial heap is actually the process of adjusting the heap, but constructing the initial heap is to adjust all non-leaf nodes.

Let's look at an example of a large top heap.

We can see that this is a big top heap. In fact, it is a representation of a binary tree, but compared with an ordinary binary tree, each non-leaf node of this type of binary tree is larger than its child node.

Next, we will use a diagram to see how to construct a large top heap.

Initial sequence: 10 6 8 7 3 30

Initial binary tree:

Start adjusting from the first non-leaf node

Before adjustment

After adjustment

Then adjust forward

forward

back

forward

back

Since nodes 30 and 10 are swapped, it is very likely that the last sub-binary tree does not satisfy the properties of a max-heap, so it needs to be adjusted downward to convert it into a max-heap.

Fortunately, in this example 10---8 satisfies the properties of a max-heap.

If you change 8 to 11, you have to adjust it again

The above is the construction process of the entire big top heap.

After constructing the max-heap, we can see that the top node is the node with the largest value in the entire binary tree, so we swap the top node with the last leaf node.

Then we can delete the last leaf node from the sequence (this is only a logical deletion, not a physical deletion. This means that in the subsequent heap adjustment, the node will no longer participate in the comparison and adjustment).

We can see that after the swap, the binary tree no longer conforms to the properties of the max-heap, so we need to adjust it again.

Adjust from the top node downwards

At this point, we can see that the conditions for a max-heap have been met. Now swap the top node and the last leaf node again (note: the last leaf node is no longer 30, but 3. This is because we have logically deleted 30)

After the swap is completed

Then follow the above steps again to adjust and swap until the entire sequence is logically deleted.

The entire sorting process is completed.

Next we use PHP code to implement the big top heap sort.

/**
 * 交换函数
 */
function swap(&$arr,$a,$b){
    $t = $arr[$a];
    $arr[$a] = $arr[$b];
    $arr[$b] = $t;
}
/**
 * 调整一个节点和其左右子节点满足大顶堆的性质
 */
function MakeHeapChild(&$arr,$pos,$end){
    $p = false;
    if($pos*2+1 <= $end){
        //左右子节点相比较，找出最大节点
        if($arr[$pos*2-1]>=$arr[$pos*2]){
            $p = $pos*2;
        }else{
            $p = $pos*2+1;
        }
    }elseif($pos*2<=$end){
        $p = $pos*2;
    }
    if(!$p) return $p;
    //比较当前节点和其最大的子节点
    if($arr[$pos-1]<=$arr[$p-1]){
        swap($arr,$pos-1,$p-1);
        return $p;
    }
    return false;
   
}
function HeapSort(&$arr){
    $start = floor(count($arr)/2); //找到最后一个非叶子节点
    $end = count($arr);
    /*
     * 构造大顶堆
     */
    while($start>0){
        $p = $start;
        while($p){
            $p = MakeHeapChild($arr,$p,$end);
        }
        $start-- ;
    }
    //构造大顶堆结束
    /*
     * 交换顶部节点和最后一个叶子节点 依次调整大顶堆
     */
    while($end>1){
        swap($arr,0,$end-1);
        $end--;
        $p = 1;
        while($p){
            $p = MakeHeapChild($arr,$p,$end);
        }
    }
}
$arr = array(10,6,8,23,4,1,17,56,32,50,11,9);
HeapSort($arr);
print_r($arr);

In fact, the steps and codes for constructing a small top heap are similar to the above steps. Based on the above code, we can modify the MakeHeapChild function to change the big top heap into a small top heap, and the ascending sort can be changed to descending sort.

function MakeHeapChild(&$arr,$pos,$end){
    $p = false;
    if($pos*2+1 <= $end){
        //左右子节点相比较，找出最大节点
        if($arr[$pos*2-1] < $arr[$pos*2]){   //修改一  将 >= 改成 <
            $p = $pos*2;
        }else{
            $p = $pos*2+1;
        }
    }elseif($pos*2<=$end){
        $p = $pos*2;
    }
    if(!$p) return $p;
    //比较当前节点和其最大的子节点
    if($arr[$pos-1] > $arr[$p-1]){      //修改二  将 <= 改成  >
        swap($arr,$pos-1,$p-1);
        return $p;
    }
    return false;
   
}

The above are the steps and implementation code of heap sort.

The above code is not necessarily the best code, but it has described and implemented the whole heap sorting process.

I hope this helps you learn heap sorting.