滿足條件

• 需要是完全二叉樹(shù)。除了最后一層，其他層是滿的，最后一層都靠左排列。
• 每個(gè)節(jié)點(diǎn)的值必須大于等于(小于等于)其子樹(shù)的每個(gè)節(jié)點(diǎn)的值

如何存儲(chǔ)堆

使用數(shù)組

• 堆是完全二叉樹(shù)，使用數(shù)組比較節(jié)省空間。因?yàn)椴恍枰鎯?chǔ)左右子孩子節(jié)點(diǎn)的指針

• 通過(guò)數(shù)組的下標(biāo)就可以找到節(jié)點(diǎn)的父節(jié)點(diǎn)和左右孩子節(jié)點(diǎn)

  
  
  image.png
• 如果小標(biāo)從1開(kāi)始。下標(biāo)是i,左節(jié)點(diǎn)是2*i,右節(jié)點(diǎn)是2*i+1.父節(jié)點(diǎn)下標(biāo)是i/2
• 如果小標(biāo)從0開(kāi)始。如果節(jié)點(diǎn)的下標(biāo)是i，那左子節(jié)點(diǎn)的下標(biāo)就是2i+1，右子節(jié)點(diǎn)的下標(biāo)就是2i+2，父節(jié)點(diǎn)的下標(biāo)就是(i-1)/2
• 這里講解和Demo都是從下標(biāo)1開(kāi)始

插入數(shù)據(jù)

• 把元素插入到最后一個(gè)位置
• 讓插入的元素和父節(jié)點(diǎn)比較，如果不滿足子節(jié)點(diǎn)小于等于夫節(jié)點(diǎn)，就互換節(jié)點(diǎn)。一直重復(fù)之到堆頂。從下向上堆化

• 時(shí)間復(fù)雜度O(logn)

  
  
  image.png

image.png

func (heap *Heap) Insert(item int) error {
    if heap.count >= heap.capacity {
        return fmt.Errorf("heap is full")
    }
    heap.count++
    //1. 放到最后
    heap.array[heap.count] = item
    i := heap.count
    //從下向上堆化
    //i/2:父節(jié)點(diǎn) 直到小于等于父節(jié)點(diǎn),或者到了根節(jié)點(diǎn)
    for i/2 > 0 && heap.array[i] > heap.array[i/2] {
        swap(heap.array, i, i/2)
        i = i / 2
    }
    return nil
}

刪除堆頂元素

• 錯(cuò)誤做法
  直接刪除堆頂元素，找出左右節(jié)點(diǎn)中大值，替換父節(jié)點(diǎn)。依次遞歸操作直到葉子節(jié)點(diǎn)。這樣會(huì)造成不是一個(gè)完全二叉樹(shù)。

  
  
  image.png

• 正確做法
  把最后一個(gè)節(jié)點(diǎn)放到堆頂，從上到下，依次遞歸比較和父子節(jié)點(diǎn)，如果不滿足父子節(jié)點(diǎn)之間的關(guān)系，互換兩個(gè)節(jié)點(diǎn)。知道父子節(jié)點(diǎn)滿足大小關(guān)系。
  因?yàn)槲覀兪且瞥淖詈蟮囊粋€(gè)節(jié)點(diǎn)，在堆化操作中都是互換，不會(huì)出現(xiàn)數(shù)組空洞，堆化完成肯定滿足完全二叉樹(shù)

• 時(shí)間復(fù)雜度O(logn)

  
  
  image.png

func (heap *Heap) RemoveRoot() error {
    if heap.count <= 0 {
        return fmt.Errorf("heap is empty")
    }

    //1.把最后一個(gè)節(jié)點(diǎn)賦值個(gè)根節(jié)點(diǎn)
    heap.array[1] = heap.array[heap.count]
    heap.array[heap.count] = 0
    heap.count--
    heapify(heap.array, heap.count, 1)
    return nil
}

/**
  從上向下堆化
*/
func heapify(slice []int, count int, startIndex int) {
    for {
        maxIndex := startIndex
        //節(jié)點(diǎn)和自己的左右節(jié)點(diǎn)比較,找出最大的
        if startIndex*2 <= count && slice[maxIndex] < slice[startIndex*2] {
            maxIndex = startIndex * 2
        }

        if startIndex*2+1 <= count && slice[maxIndex] < slice[startIndex*2+1] {
            maxIndex = startIndex*2 + 1
        }

        if maxIndex == startIndex {
            //發(fā)現(xiàn)節(jié)點(diǎn)已經(jīng)比自己左右節(jié)點(diǎn)大了，堆化完成
            break
        }
        //交互節(jié)點(diǎn)數(shù)據(jù)
        swap(slice, startIndex, maxIndex)
        //繼續(xù)向下堆化
        startIndex = maxIndex
    }
}

在原有數(shù)組上建堆

• 在數(shù)組上從后向前
• 從上向下堆化
• 葉子節(jié)點(diǎn)向下堆化只能和自己比較，葉子節(jié)點(diǎn)不參與

• 時(shí)間復(fù)雜度O(n)

  
  
  image.png
  
  
  image.png

func BuildHeap(array []int, count int) *Heap {
    heap := NewHeap(count)
    //把數(shù)組轉(zhuǎn)換成從1開(kāi)始
    for i := 0; i < count; i++ {
        heap.array[i+1] = array[i]
    }

    //從非葉子節(jié)點(diǎn)開(kāi)始(葉子節(jié)點(diǎn)向下堆化只能和自己比較沒(méi)有意義)，從上向下堆化。直到根節(jié)點(diǎn)(包含)
    //堆是完全二叉樹(shù)，所以count / 2之后的節(jié)點(diǎn)都是葉子節(jié)點(diǎn)
    for i := count / 2; i >= 1; i-- {
        heapify(heap.array, count, i)
    }
    return heap
}

堆排序

• 建堆
• 堆頂元素和最后一個(gè)元素互換，最大值就到了最后。然后對(duì)n-1的堆進(jìn)行進(jìn)行從節(jié)點(diǎn)開(kāi)始從上向下進(jìn)行堆化。完成后把堆頂元素和n-1進(jìn)行互換。重復(fù)上面的步驟一直到只有一個(gè)元素。就完成了排序
• 時(shí)間復(fù)雜度O(nlogn)
• 不穩(wěn)定

func Sort(slice []int, count int) []int {
    //1. 建堆
    heap := BuildHeap(slice, count)
    for k := count; k > 1; {
        //2. 每次都把堆頂元素移動(dòng)到最后
        swap(heap.array, 1, k)
        k--
        //3. 堆化剩余的元素，直到剩下一個(gè)元素
        heapify(heap.array, k, 1)
    }

    return heap.array
}
/**
  從上向下堆化
*/
func heapify(slice []int, count int, startIndex int) {
    for {
        maxIndex := startIndex
        //節(jié)點(diǎn)和自己的左右節(jié)點(diǎn)比較,找出最大的
        if startIndex*2 <= count && slice[maxIndex] < slice[startIndex*2] {
            maxIndex = startIndex * 2
        }

        if startIndex*2+1 <= count && slice[maxIndex] < slice[startIndex*2+1] {
            maxIndex = startIndex*2 + 1
        }

        if maxIndex == startIndex {
            //發(fā)現(xiàn)節(jié)點(diǎn)已經(jīng)比自己左右節(jié)點(diǎn)大了，堆化完成
            break
        }
        //交互節(jié)點(diǎn)數(shù)據(jù)
        swap(slice, startIndex, maxIndex)
        //繼續(xù)向下堆化
        startIndex = maxIndex
    }
}

和快排的比較

• 堆排的數(shù)據(jù)讀取開(kāi)銷比較大
  對(duì)于快排，數(shù)據(jù)是順序訪問(wèn)的。對(duì)于堆排，數(shù)據(jù)是跳的訪問(wèn)的。
  在計(jì)算機(jī)進(jìn)行運(yùn)算的時(shí)候，數(shù)據(jù)不一定會(huì)從內(nèi)存讀取出來(lái)，而是從一種叫cache的存儲(chǔ)單位讀取。原因是cache相比內(nèi)存，讀取速度非?？?，所以cache會(huì)把一部分我們經(jīng)常讀取的數(shù)據(jù)暫時(shí)儲(chǔ)存起來(lái)，以便下一次讀取的時(shí)候，可以不必跑到內(nèi)存去讀，而是直接在cache里面找。一般認(rèn)為讀取數(shù)據(jù)遵從兩個(gè)原則：temporal locality，也就是不久前讀取過(guò)的一個(gè)數(shù)據(jù)，在之后很可能還會(huì)被讀取一遍；另一個(gè)叫spatial locality，也就是說(shuō)讀取一個(gè)數(shù)據(jù)，在它周圍內(nèi)存地址存儲(chǔ)的數(shù)據(jù)也很有可能被讀取到。因此，在讀取一個(gè)單位的數(shù)據(jù)(比如1個(gè)word)之后，不光單個(gè)word會(huì)被存入cache，與之內(nèi)存地址相鄰的幾個(gè)word，都會(huì)以一個(gè)block為單位存入cache中。
  為什么在平均情況下快速排序比堆排序要優(yōu)秀

• 對(duì)于同樣的數(shù)據(jù)，在排序過(guò)程中，堆排序算法的數(shù)據(jù)交換次數(shù)要多于快速排序
  我們?cè)谥v排序的時(shí)候，提過(guò)兩個(gè)概念，有序度和逆序度。對(duì)于基于比較的排序算法來(lái)說(shuō)，整個(gè)排序過(guò)程就是由兩個(gè)基本的操作組成的，比較和交換（或移動(dòng)）。
  快速排序數(shù)據(jù)交換的次數(shù)不會(huì)比逆序度多。
  但是堆排序的第一步是建堆，建堆的過(guò)程會(huì)打亂數(shù)據(jù)原有的相對(duì)先后順序，導(dǎo)致原數(shù)據(jù)的有序度降低。比如，對(duì)于一組已經(jīng)有序的數(shù)據(jù)來(lái)說(shuō)，經(jīng)過(guò)建堆之后，數(shù)
  據(jù)反而變得更無(wú)序了