Package Arrangement

Keywords: Queue, Stack, Binary Tree (search, insert, delete, remove, balance)

Usage

See Problem Statement

Problem statements

• L production lines
• N packages
• O Operations

Strategy

• Production line

  • Binomial Max Heap
    • Doubly linked list
  • Deque
    • First-in-First out
    • Doubly Linked list

      struct
        int[] array
        int* next_array
        int* prev_array
      end

      

• Peaking a production line

  • getFirst: O(1)
  • getLast: O(1)
  • getMax: O(1)

• Operation

  • PopFirst: O(n)
  • PopLast: O(n)
  • PopMax: O(log n)

• Merge Production line

  • Deque

Queue

Stack

Binary Tree Operation

What is a "balanced" binary tree?

Ref:

• Balancing a binary search tree (GO)

AVL Tree

Ref

• Balancing a binary search tree (GO)
• AVL Tree: Insertion (GreekforGeek)
• AVL Tree: Deletion (GreekforGeek)
• 資料結構與演算法：AVL Tree

Time complexity with AVL Tree

Operation	Time
Search	O(log n)
Insert	O(log n)
Delete	O(log n)

• Advantage of using AVL Tree
  • Guarantee: O(log n) for binary search

Ref:

• 資料結構與演算法：AVL Tree

Idea

• Merge 要求 log(n)

Hints

• 用 Heap: 快速找到 max, first, last
• Time complexity of merge: <O(n)
  • 方法: https://abitofcs.blogspot.com/2019/06/merging-heaps-in-olog-n.html
  • https://cs.stackexchange.com/questions/82793/merge-2-binary-heaps
  • https://medium.com/100-days-of-python/day-06-binomial-heap-88ca2edb8255
  • https://en.m.wikipedia.org/wiki/Binomial_heap

Heap Operations

Free a binary tree

deallocate (node):
    //do nothing if passed a non-existent node
    if node is null
        return

    //now onto the recursion
    deallocate(left node)
    deallocate(right node)

    free node

Ref: stackoverflow

Returning a void function

Ref: web

Function pointer

#include <stdio.h>
// A normal function with an int parameter
// and void return type
void fun(int a)
{
    printf("Value of a is %d\n", a);
}
  
int main()
{ 
    void (*fun_ptr)(int) = fun;  // & removed
  
    fun_ptr(10);  // * removed
  
    return 0;
}

Ref: GreekforGeek

Array of function pointers

int (*fun[3])(packData, int)=  {PeekFirstPack, PeekLastPack, PeekMaxPack};

What are Mutually Dependent Structures in C?

• Partial declaration

• Ref: What are Mutually Dependent Structures in C?

Leftist tree

Ref:

1. https://tmt514.gitbooks.io/2016-09/content/tree-ds/leftist-tree.html
2. http://sunmoon-template.blogspot.com/2014/12/leftist-tree.html
3. https://www.humblec.com/c-implementation-leftist-tree/
4. Tutorial: Leftist Tree

References

1. Stack, Queue and Heap. [GitBook]