Binomial heap

optimization of max heap

  • priority queue review: max heap

    • insert: Lesson 10 Binomial heap and hash table - 图1#card=math&code=O%28log%20n%29)
    • removeMax: Lesson 10 Binomial heap and hash table - 图2#card=math&code=O%28log%20n%29)

  • Question: How to optimize? (make insert Lesson 10 Binomial heap and hash table - 图3#card=math&code=O%281%29))

    • Hard if every operation Lesson 10 Binomial heap and hash table - 图4#card=math&code=O%281%29)
    • Possible if “amortized” Lesson 10 Binomial heap and hash table - 图5#card=math&code=O%281%29) (solution similar to extendable array)

  • Solution

    • cheap insertion usually Lesson 10 Binomial heap and hash table - 图6 insertion to “small” tree usually
    • expensive insertion sometimes Lesson 10 Binomial heap and hash table - 图7 insertion to “big tree” sometimes
    • This structure is called “forest”

binomial tree

  • structure:
    Lesson 10 Binomial heap and hash table - 图8
    |Lesson 10 Binomial heap and hash table - 图9|1 node||
    |——|——|——|
    |Lesson 10 Binomial heap and hash table - 图10|2 nodes|2Lesson 10 Binomial heap and hash table - 图11|
    |Lesson 10 Binomial heap and hash table - 图12|4 nodes|2Lesson 10 Binomial heap and hash table - 图13|
    |Lesson 10 Binomial heap and hash table - 图14|8 nodes|2Lesson 10 Binomial heap and hash table - 图15|
    |…|…|…|
    |Lesson 10 Binomial heap and hash table - 图16|Lesson 10 Binomial heap and hash table - 图17 nodes|2Lesson 10 Binomial heap and hash table - 图18|

  • summarize
    Lesson 10 Binomial heap and hash table - 图19

Change the bionomial tree to a heap

binomial tree Lesson 10 Binomial heap and hash table - 图20 multi-tree

  • max-tree property

  • bionomial forest + max-trees

    • at most one Lesson 10 Binomial heap and hash table - 图21 per each k
      Lesson 10 Binomial heap and hash table - 图22 can represent any Lesson 10 Binomial heap and hash table - 图23:
      example: n=10 (Lesson 10 Binomial heap and hash table - 图24) + 2(Lesson 10 Binomial heap and hash table - 图25)
  • binomial heap

Lesson 10 Binomial heap and hash table - 图26

  • Analysis
    insert n nodes:

n insert Lesson 10 Binomial heap and hash table - 图27 Lesson 10 Binomial heap and hash table - 图28#card=math&code=O%28n%29)
Lesson 10 Binomial heap and hash table - 图29 merge Lesson 10 Binomial heap and hash table - 图30
Lesson 10 Binomial heap and hash table - 图31 merge Lesson 10 Binomial heap and hash table - 图32 Lesson 10 Binomial heap and hash table - 图33#card=math&code=O%28n%29)
Lesson 10 Binomial heap and hash table - 图34 merge Lesson 10 Binomial heap and hash table - 图35 /
amortized complexity: Lesson 10 Binomial heap and hash table - 图36#card=math&code=O%281%29)
search comlexity: Lesson 10 Binomial heap and hash table - 图37#card=math&code=O%28log%20n%29)

explanation: binary system representation

Hash Map

Definition

  • priority queue:

    • A.removeMax() fast
    • A.insert(key,data) fast
    • category: heap, binomial heap,…

  • map

    • A.insert(key, data) fast
    • A.remove(key) fast
      Lesson 10 Binomial heap and hash table - 图38
      Lesson 10 Binomial heap and hash table - 图39
      Lesson 10 Binomial heap and hash table - 图40
    • key:ordered/unordered (int/string)

How to realize Hash map

  • linked list: (key, value) | | insert | get | | —- | —- | —- | | unordered key | Lesson 10 Binomial heap and hash table - 图41#card=math&code=O%281%29) | Lesson 10 Binomial heap and hash table - 图42#card=math&code=O%28n%29) | | ordered key | Lesson 10 Binomial heap and hash table - 图43#card=math&code=O%28n%29) | Lesson 10 Binomial heap and hash table - 图44#card=math&code=O%28n%29) |
  • array | | insert | get | | —- | —- | —- | | unordered key | Lesson 10 Binomial heap and hash table - 图45#card=math&code=O%281%29) | Lesson 10 Binomial heap and hash table - 图46#card=math&code=O%28n%29) | | ordered key | Lesson 10 Binomial heap and hash table - 图47#card=math&code=O%28n%29) | Lesson 10 Binomial heap and hash table - 图48#card=math&code=O%28log%20n%29) |
  • key Lesson 10 Binomial heap and hash table - 图49 (small)integer
    key as array index, value as array data | | insert | get | | —- | —- | —- | | key | Lesson 10 Binomial heap and hash table - 图50#card=math&code=O%281%29) | Lesson 10 Binomial heap and hash table - 图51#card=math&code=O%281%29) |

non-small integer key Lesson 10 Binomial heap and hash table - 图52 need super big array(space)

  • key convert: string to int
  • key compress: reduce space

Lesson 10 Binomial heap and hash table - 图53

  • A.insert(key, value) Lesson 10 Binomial heap and hash table - 图54 A[h(key)] = value
  • v = A.get(key) Lesson 10 Binomial heap and hash table - 图55 v = A[h(key)]

A: bucket hash
h: array function

In most circumstance, keys > K

  • two keys of same Lesson 10 Binomial heap and hash table - 图56
  • collision

Hash Code

  • str “apple”

      1. HashCode(str) = str[0] -‘a’ Lesson 10 Binomial heap and hash table - 图57
        HashCode(“apple”) = HashCode(“act”)
      1. HashCode(str) = Lesson 10 Binomial heap and hash table - 图58#card=math&code=%5Csum_%7Bi%7D%20%28str%5Bi%5D-%27a%27%29)
        %100 (compress) Lesson 10 Binomial heap and hash table - 图59