图解-堆插入节点

转自：http://www.mathcs.emory.edu/~cheung/Courses/171/Syllabus/9-BinTree/heap-insert.html

• Inserting a value into a Heap

   

   

  ---

  ---

  ---

  ---

   

  • Problem description:

     

    You are given a heap. For example:       You are also given a value x For example: x = 3     Problem:   Insert the value x into the heap (so that the resulting tree is also a heap !!!)

     

    ---

     

  • Here is a Heap containing the inserted value 3:

     

    Heap before inserting the value 3
    Heap after inserting the value 3

    $64,000 question:

     

    How did you do it ???

     

• The insert algorithm for a Heap

   

   

  ---

  ---

  ---

  ---

   

  • The heap insertion algorithm in pseudo code:

     

    Insert a node containing the insertion value in the "fartest left location" of the lowest level of the Binary Tree Filter the inserted node up using this algorithm: while ( inserted node's value < value in its parent node ) { swap the values of the respective node; }

     

    ---

     

  • Example:

     

    Insert the value 3 into the following heap:       Step 1: Insert a node containing the insertion value (= 3) in the "fartest left location" of the lowest level       Step 2: Filter the inserted node up the tree   Compare the values of the inserted node with its parent node in the tree:       3 is smaller than its parent value (11): swap !!!   Repeat !     Compare the values of the inserted node with its parent node in the tree:       3 is smaller than its parent value (5): swap !!!   Repeat !     Compare the values of the inserted node with its parent node in the tree:       The parent node has a smaller value, so 3 is in its correct place !!! We are done. The result is a good heap:

     

    ---

    ---

     

  • Heap insertion algorithm in Java:

     

    void put( double x ) { a[NNodes+1] = x; // Insert x in the "fartest left location" // This preserves the "complete bin tree" prop NNodes++; // We have 1 more node HeapFilterUp( NNodes ); // Filter the inserted node // The FilterUp() method need to know // which node is the inserted node !!! // The parameter NNodes identifies the // inserted node a[NNodes] }

     

    ---

     

  • The Filter Up algorithm in pseudo code:

     

    HeapFilterUp( k ) // Filter up the node a[k] { while ( k has a parent node ) { parent = k/2; // a[parent] is the parent node of a[k] if ( a[k] < a[parent] ) { swap a[k] <--> a[parent]; k = parent; } else { break; // a[k] is in correct position, DONE ! } }

     

    ---

     

  • The Filter up algorithm (describe above) is coded as a method:

     

    /* =================================================== HeapFilterUp(k): Filters the node a[k] up the heap =================================================== */ void HeapFilterUp( int k ) { int parent; // parent = parent node of k double help; // Used for swapping while ( parent > 0 ) // parent == 0 means no parent { parent = k/2; // Find parent node of k if ( a[k] < a[parent] ) { /* ===================================== Wrong order: swap a[k] and a[parent] ===================================== */ help = a[parent]; a[parent] = a[k]; a[k] = help; /* ------------------------------ Continue one level in the tree ------------------------------ */ k = parent; } else { break; // k is in correct position - DONE ! } } }

     

    ---

     

  • Example Program: (Demo above code)                                                 

     

    How to run the program:

     

    Right click on link and save in a scratch directory   To compile:   javac testProg.java To run:          java testProg

     

    • The Heap class Prog file: click here
    • The test Prog file: click here
• Running time analysis of the heap insert algorithm

   

   

  ---

  ---

  ---

  ---

   

  • Before we can perform a running time analysis, we must first understand how the algorithm works exactly...

     

    ---

     

  • Summary of the heap insert algorithm:

     

    The node is always inserted as the left most leaf node:       The the HeapFilterUp() algorithm will migrate the insert node up into the binary tree:   and:

     

    ---

    ---

     

  • Fact:

     

    The number of times that the inserted node will migrate up into the binary tree is:   # migrations ≤ height of the binary tree

    Example:

     

    The maximum number of this that node 3 can move up in this binary tree:   is at most 3 times:

     

    ---

    ---

     

  • Therefore:

     

    Running time( insert(n) ) = Running time heap insert in heap with n node = height of a heap of n nodes

     

• The height of a heap when it contains n nodes

   

   

  ---

  ---

  ---

  ---

   

  • Recall:

     

    A perfect binary tree of height h has:   2h+1 − 1 nodes          (See: click here )   Similarly, a perfect binary tree of height h−1 has:   2h − 1 nodes          (See: click here )

     

    ---

     

  • Fact:

     

    (A heap is a complete binary tree) The number of nodes n in a complete binary tree (i.e., a heap) of height h is between:   2h − 1 < n ≤ 2h+1 − 1

    Proof:

     

    A complete binary tree of height h:   will have more nodes than a perfect binary tree of height h−1:   and it will have at most as many nodes as a perfect binary tree of height h:

    Therefore:

     

    Let: n = # nodes in heap of height h 2h - 1 < n ≤ 2h+1 − 1 <===> 2h < n + 1 ≤ 2h+1 <===> h < lg(n + 1) ≤ h+1 ===> height of heap ~= lg(n + 1)

     

• Running time of the heap insert algorithm

   

  • Summary:

     

    Running time of insert into a heap of n nodes = height of the heap     height of the heap containing n nodes ~= lg(n + 1)

     

    ---

     

  • Conclusion:

     

    Running time of insert into a heap of n nodes = O(lg(n))