Chapter 22: The Heap Data Structure

前言

Heap資料結構是用來依序找出資料中最高(低)優先權的元素,優先權的定義是依照不同資料性質而定。

大綱

  • What is a heap?

  • The heap property

  • Heap applications

  • Common heap operations

  • How do you represent a heap?

  • Removing from a heap

    • Implementation of remove

  • Inserting into a heap

    • Implementation of insert

  • Removing from an arbitrary index

  • Searching for an element in a heap

  • Building a heap

  • Testing

What is a heap?

  • Heap是一個complete binary tree, 所以跟tree一樣可以用一個array來進行構建。

    • Max Heap: elements with a higher value have a higher priority.

    • Min heap: elements with a lower value have a higher priority.

The heap property

  • Heap主要的兩個特性

    • Max Heap, 父節點的值一定大於或等於子節點的值,Min heap則相反。

    • Complete binary tree, 除了葉節點那層level以外,其他level節點數目必須是長齊的。

Heap applications

  • Calculating the minimum or maximum element of a collection.

  • Heap sort.(CH32)

  • Constructing a priority queue.(CH24)

  • Constructing graph algorithms, like Prim’s or Dijkstra’s, with a priority queue.(CH42,44)

How do you represent a heap?

  • 給一個node其index = i, 則

    • Left child = 2i + 1

    • Right child = 2i + 2

Traversing down an actual binary tree to get the left and right child of a node is a O(log n) operation. In a random-access data structure, such as an array, that same operation is just O(1).

Removing from a heap

  • Step1: 將root跟heap中最後一個元素對調

  • Step2: 移除最後一個元素

  • Step3: 調整heap, 由頂端root逐層向下調整(sift down), 維持heap特性

Inserting into a heap

  • Step1: 將要插入元素放到heap中最後一個

  • Step2: 調整heap, 由底端葉子逐層向上調整(sift up), 維持heap特性

Removing from an arbitrary index

​ 如果刪除的節點是葉子層(5),那就需要做siftUp

如果刪除的節點不是葉子層(7),那就需要做siftDown

Searching for an element in a heap

heaps are not designed for fast searches. With a binary search tree, you can perform a search in O(log n) time, but since heaps are built using an array, and the node ordering in an array is different, you can’t even perform a binary search.

  • the worst-case, an O(n) operation

Building a heap

loop through the array backwards, starting from the first non-leaf node, and sift down all parent nodes.

Testing

Last updated