堆排序的實(shí)現(xiàn)原理是什么

本篇文章給大家分享的是有關(guān)堆排序的實(shí)現(xiàn)原理是什么，小編覺得挺實(shí)用的，因此分享給大家學(xué)習(xí)，希望大家閱讀完這篇文章后可以有所收獲，話不多說，跟著小編一起來看看吧。

對(duì)于堆排序會(huì)涉及一些完全二叉樹知識(shí)。對(duì)于待排序列{10, 2, 11, 8, 7}，把它看成是一顆完全二叉樹，如下圖所示。

堆分為大根堆和小根堆：大根堆表示每個(gè)根節(jié)點(diǎn)均大于其子節(jié)點(diǎn)（L(i) >= L(2i) && L(i) >= L(2i + 1)），小根堆表示每個(gè)根節(jié)點(diǎn)均小于其子節(jié)點(diǎn)（L(i) <= L(2i) && L(i) <= L(2i + 1)）。（在完全二叉樹中第i個(gè)節(jié)點(diǎn)的左子節(jié)點(diǎn)為2i，其右字節(jié)點(diǎn)為2i + 1）

本文將以大根堆的構(gòu)建作為示例進(jìn)行講解。

堆排序的第一步——構(gòu)建初始堆。如何構(gòu)建初始堆呢？根據(jù)定義，關(guān)鍵點(diǎn)在于每個(gè)根節(jié)點(diǎn)。觀察上述待排序列的完全二叉樹，不難發(fā)現(xiàn)存在節(jié)點(diǎn)2和節(jié)點(diǎn)10有子節(jié)點(diǎn)，它們是需要關(guān)注的節(jié)點(diǎn)。

如何定位節(jié)點(diǎn)2呢？發(fā)現(xiàn)它是葉子節(jié)點(diǎn)，或者最后一個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)，根據(jù)完全二叉樹的性質(zhì)可知，除根節(jié)點(diǎn)外任意節(jié)點(diǎn)的父節(jié)點(diǎn)的編號(hào)為&#8970;n / 2&#8971;。已知n = 5，易知節(jié)點(diǎn)2的編號(hào)為&#8970;5 / 2&#8971; = ②。比較它與左右子節(jié)點(diǎn)的大小并調(diào)整。

最后剩下根節(jié)點(diǎn)10，已知節(jié)點(diǎn)2的編號(hào)為②，② - 1 = ①即得到根節(jié)點(diǎn)10的編號(hào)。比較它與左右子節(jié)點(diǎn)的大小并調(diào)整。

調(diào)整完畢后發(fā)現(xiàn)已經(jīng)構(gòu)成了一個(gè)“大根堆”，示例中的待排序列較為簡(jiǎn)單，再給出一個(gè)較為復(fù)雜的待排序列，觀察其構(gòu)建大根堆的過程。對(duì)于待排序列{53, 17, 78, 09, 45, 65, 87, 32}，將它看成一顆完全二叉樹。

同樣我們來看它所需要關(guān)注的節(jié)點(diǎn)有哪些。

根據(jù)第一個(gè)例子，我們很容易能定位節(jié)點(diǎn)09的編號(hào)為&#8970;8 / 2&#8971; = ④，節(jié)點(diǎn)78的編號(hào)為④ - 1 = ③……，依次類推，發(fā)現(xiàn)了一定的規(guī)律，即需要調(diào)整的節(jié)點(diǎn)位置從&#8970;n / 2&#8971;開始依次遞減直到根節(jié)點(diǎn)①結(jié)束(&#8970;n / 2&#8971; ~ 1)?，F(xiàn)在開始調(diào)整。

在第四次調(diào)整結(jié)束后發(fā)現(xiàn)節(jié)點(diǎn)53不滿足大根堆的定義，其右子節(jié)點(diǎn)大于它，此時(shí)需要做進(jìn)一步的向下調(diào)整。

注意向下調(diào)整是每次向上調(diào)整的時(shí)候都需要做的判斷是否需要向下調(diào)整，而不是在所有的向上調(diào)整結(jié)束過后再回過頭來向下調(diào)整。這樣大根堆就建立好了，此時(shí)待排序列數(shù)組情況已經(jīng)發(fā)生了改變：{87, 45, 78, 32, 17, 65, 53, 09}。接下來是如何進(jìn)行排序的問題。將大根堆的根節(jié)點(diǎn)與最后一個(gè)節(jié)點(diǎn)互換，并調(diào)整二叉樹使其仍然滿足大根堆。

可以看到將根節(jié)點(diǎn)與最后一個(gè)節(jié)點(diǎn)呼喚后，待排序列的最大值已經(jīng)放到了數(shù)組的最后一個(gè)位置{……, 87}，此時(shí)完成了第一趟排序，但這第一趟排序還沒有結(jié)束，此時(shí)除節(jié)點(diǎn)87外，其余節(jié)點(diǎn)并不滿足大根堆的條件，所以需要對(duì)其余節(jié)點(diǎn)進(jìn)行調(diào)整為大根堆。排序過程不再給出，Java和Python3的代碼實(shí)現(xiàn)如下。

Java

package com.algorithm.sort.heap;

import java.util.Arrays;

/**
 * 堆排序
 * Created by yulinfeng on 6/20/17.
 */
public class Heap {
  
  public static void main(String[] args) {
    int[] nums = {53, 17, 78, 09, 45, 65, 87, 32};
    nums = heapSort(nums);
    System.out.println(Arrays.toString(nums));
  }
  
  /**
   * 堆排序
   * @param nums 待排序數(shù)組序列
   * @return 排好序的數(shù)組序列
   */
  private static int[] heapSort(int[] nums) {
  
    for (int i = nums.length / 2 - 1; i >= 0; i--) {
      heapAdjust(nums, i, nums.length);
    }
    for (int i = nums.length - 1; i > 0; i--) {
      int temp = nums[i];
      nums[i] = nums[0];
      nums[0] = temp;
      heapAdjust(nums, 0, i);
    }
    return nums;
  }
  
  /**
   * 調(diào)整堆
   *
   * @param nums  待排序序列
   * @param parent   待調(diào)整根節(jié)點(diǎn)
   * @param length 數(shù)組序列長(zhǎng)度
   */
  private static void heapAdjust(int[] nums, int parent, int length) {
    int temp = nums[parent];
    int childIndex = 2 * parent + 1;  //完全二叉樹節(jié)點(diǎn)i從編號(hào)1開始的左子節(jié)點(diǎn)位置在2i，此處數(shù)組下標(biāo)從0開始，即左子節(jié)點(diǎn)所在數(shù)組索引位置為：2i + 1
    while (childIndex < length) {
      if (childIndex + 1 < length && nums[childIndex] < nums[childIndex + 1]) {
        childIndex++;  //節(jié)點(diǎn)有右子節(jié)點(diǎn)，且右子節(jié)點(diǎn)大于左子節(jié)點(diǎn)，則選取右子節(jié)點(diǎn)
      }
      if (temp > nums[childIndex]) {
        break; //如果選中節(jié)點(diǎn)大于其子節(jié)點(diǎn)，直接返回
      }
      nums[parent] = nums[childIndex];
      parent = childIndex;
      childIndex = 2 * parent + 1;  //繼續(xù)向下調(diào)整
    }
    nums[parent] = temp;
  }
}

Python3

#堆排序
def heap_sort(nums):

  for i in range(int(len(nums) / 2 - 1), -1, -1):
    heap_adjust(nums, i, len(nums))
  
  for i in range(len(nums) - 1, -1, -1):
    temp = nums[i]
    nums[i] = nums[0]
    nums[0] = temp
    heap_adjust(nums, 0, i)
  
  return nums

#調(diào)整堆
def heap_adjust(nums, parent, length):
  
  temp = nums[parent]
  childIndex = 2 * parent + 1
  while childIndex < length:
    if childIndex + 1 < length and nums[childIndex] < nums[childIndex + 1]:
      childIndex += 1
    if temp > nums[childIndex]:
      break
    nums[parent] = nums[childIndex]
    parent = childIndex
    childIndex = 2 * parent + 1
  
  nums[parent] = temp
    
nums = [53, 17, 78, 09, 45, 65, 87, 32]
nums = heap_sort(nums)
print(nums)

以上就是堆排序的實(shí)現(xiàn)原理是什么，小編相信有部分知識(shí)點(diǎn)可能是我們?nèi)粘９ぷ鲿?huì)見到或用到的。希望你能通過這篇文章學(xué)到更多知識(shí)。更多詳情敬請(qǐng)關(guān)注億速云行業(yè)資訊頻道。