heap結構

• heap結構
• 主要大綱(學習點)
• useful video
• useful
• compare heap and binary search tree
• Types of Heap Data Structure
• two method to build a heap
• heap sort
• heap implement

主要大綱(學習點)

1. max 和min 兩種heap
2. 如何建立heap (from array to heap )
3. 如何用heap 結構排序

useful video

可以觀看以下影片

useful

https://clu.gitbook.io/data-structure-note/heap-tree

compare heap and binary search tree

1. The fundamental distinction is that whereas the Binary Search Tree does not allow duplicates, the Heap allows. The BST is ordered, while Heap is not. So, if order is important, BST is the way to go.
2. Since heaps are complete binary trees, the height of a tree with N nodes has O(logN) height.

Types of Heap Data Structure

Generally, Heaps can be of two types:

if the original form dose not match the form of heap, we can use buttom up and top down method to build the heap form

1. Max-Heap: In a Max-Heap the key present at the root node must be greatest among the keys present at all of it’s children. The same property must be recursively true for all sub-trees in that Binary Tree.
2. Min-Heap: In a Min-Heap the key present at the root node must be minimum among the keys present at all of it’s children. The same property must be recursively true for all sub-trees in that Binary Tree.
   

two method to build a heap

1. bottum up ：插入一個我們要加入的直到array 最後面(complete tree 最後)，也就是樹的最底，保持我們亂掉的heap 就是一個complete tree ，然後再用bottum up 的方法，重新整理這顆Tree

2. top down
   

heap sort

因為Heap 的root必為整個tree的最大Or 最小，所以一直repeat delete可以得到排序的結果。

https://clu.gitbook.io/data-structure-note/heap-tree

假設此處以一維陣列來儲存這棵樹, 現在要加入一個元素(12)
首先, 新加入的元素會被放到最後的葉節點

                     10
                     / \
                    /   \
                   /     \
                  /       \ 
                 /         \
                25          15
              /   \        / \
             30    26     20 29
            /  \   / \    / \
           35  40 27 28  22  12 <---這裡

然後新加入的節點會跟父節點做比對, 若小於父節點則往上升, 直至滿足堆積樹的條件為止才停下來

                     10
                     / \
                    /   \
                   /     \
                  /       \ 
                 /         \
                25          15
              /   \        / \
             30    26     12 29
            /  \   / \    / \
           35  40 27 28  22  20

                     10
                     / \
                    /   \
                   /     \
                  /       \ 
                 /         \
                25          12 <---上不去惹
              /   \        / \
             30    26     15 29
            /  \   / \    / \
           35  40 27 28  22 20

建立好堆積樹之後, 樹根一定是所有元素的最小值, 排序應用時:
將最小值取出
調整樹為最小堆積樹
不斷重複以上步驟就可達到排序的效果了, 其中, 取出最小值的做法是將樹根與最後一個葉節點做交換,然後切下葉節點, 並重新調整為堆積樹,
在這段過程中, 找出父節點跟兩個子節點中較小的一個做交換:

1. 將最小值取出(跟最後一個葉節點交換)

   ​​​​​​​              20 <---換到最上面
   ​​​​​​​              / \
   ​​​​​​​             /   \
   ​​​​​​​            /     \
   ​​​​​​​           /       \ 
   ​​​​​​​          /         \
   ​​​​​​​         25          12
   ​​​​​​​       /   \        / \
   ​​​​​​​      30    26     15 29
   ​​​​​​​     /  \   / \    / \
   ​​​​​​​    35  40 27 28  22 10 <---被換下來了
   

2.將最小值取出(拿出來)

​​​​                 20
​​​​                 / \
​​​​                /   \
​​​​               /     \
​​​​              /       \ 
​​​​             /         \
​​​​            25          12
​​​​          /   \        / \
​​​​         30    26     15 29
​​​​        /  \   / \    /
​​​​       35  40 27 28  22 

​​​​       -> 10

3. 開始調整直到變成堆積樹

   ​​​​​​​              12
   ​​​​​​​              / \
   ​​​​​​​             /   \
   ​​​​​​​            /     \
   ​​​​​​​           /       \ 
   ​​​​​​​          /         \
   ​​​​​​​         25         15
   ​​​​​​​       /   \        / \
   ​​​​​​​      30    26     20 29
   ​​​​​​​     /  \   / \    / \_________>它往下換兩次後就停住了
   ​​​​​​​    35  40 27 28  22 
   
   ​​​​​​​    -> 10
   

因為此處假設使用一維陣列來儲存堆積樹, 所以一直重複此步驟的話, 每次將葉節點跟最小值交換的動作就是把最小值放到陣列的後端, 所以到最後陣列就變成排序好的狀態了.

heap implement