hqu

README

Hight QUality, for learning data structure and algorithm

data structure: queue, stack

algorithm: quick sort, merge sort, fibonacci number, topn, topk, max income

The source code of them is simple, please do the reading.

Queue

Base on bucket. Queue has two array of buckets. One is used to store data. The another is used to reuse buckets as a freelist.

Bucket is a small array to keep some elements.

Stack

Like queue, stack also has two array of buckets.

Quick sort

A standard quick sort algorithm implementation with Go.

Merge sort

A standard merge sort algorithm implementation with Go.

Fibonacci number

I implement fibonacci number with three ways, iteration, recursion and polynomial.

1. Iteration is a for loop.
2. Recursion is a recursive function.
3. Polynomial is a polynomial formula.

TopN and TopK

Refering to divide and conquer method, resolve it with reduce and conquer method. Like quick sort, get the index in partition, and do partition again with lowindex or indexhigh based on whether the index is greater or less than the n/k.

Max income

Resolving it with dynamic programming is complicate. Refering to Introduction to Algorithm, find the right index for the max income, and then find the left index. So simple it is.

Documentation

Index

• func FiboN(n int) int
• func FiboNPolynomial(n int) int
• func FiboNRecursive(n int) int
• func MaxIncome(nums []int) int
• func MergeSort(nums []int)
• func QuickSort(nums []int)
• func TopK(arr []int, k int) (int, bool)
• func TopN(arr []int, n int) []int
• type Queue
  • func (q *Queue) Dequeue() (v interface{}, ok bool)
  • func (q *Queue) Dequeue0() (v interface{}, ok bool)
  • func (q *Queue) Enqueue(v interface{})
  • func (q *Queue) Enqueue1(v interface{}) (size int)
  • func (q *Queue) Range(handle func(v interface{}) bool)
  • func (q *Queue) Size() int
• type Queuer
• type Stack
  • func (s *Stack) Pop() (v interface{}, ok bool)
  • func (s *Stack) Push(v interface{})
  • func (s *Stack) Range(handle func(v interface{}) bool)
  • func (s *Stack) Size() int
• type Stacker

Functions

func FiboN

func FiboN(n int) int

FiboN gets the `n`th Fibonacci Number which starts with 1, 1, 2, ... with iteration.

func FiboNPolynomial

func FiboNPolynomial(n int) int

FiboNPolynomial gets the `n`th Fibonacci Number which starts with 1, 1, 2, ... with polynomial formula.

func FiboNRecursive

func FiboNRecursive(n int) int

FiboNRecursive gets the `n`th Fibonacci Number which starts with 1, 1, 2, ... with recursion.

func MaxIncome

func MaxIncome(nums []int) int

MaxIncome gets the max income from a number array

func MergeSort

func MergeSort(nums []int)

MergeSort sorts a number array with merge-sort algorithm

func QuickSort

func QuickSort(nums []int)

QuickSort sorts a number array with quick-sort algorithm

func TopK

func TopK(arr []int, k int) (int, bool)

TopK finds the `k`th greatest integers in the array `arr`.

func TopN

func TopN(arr []int, n int) []int

TopN finds the count `n` greatest integers in the array `arr`

Types

type Queue

type Queue struct {
	sync.Mutex
	// contains filtered or unexported fields
}

Queue is a high memory efficient queue. It uses bucket to cache data and reuses the buckets.

func (*Queue) Dequeue

func (q *Queue) Dequeue() (v interface{}, ok bool)

Dequeue pops a value from the queue with locking.

func (*Queue) Dequeue0

func (q *Queue) Dequeue0() (v interface{}, ok bool)

Dequeue0 pops a value from the queue without locking.

func (*Queue) Enqueue

func (q *Queue) Enqueue(v interface{})

Enqueue pushes a value into the queue.

func (*Queue) Enqueue1

func (q *Queue) Enqueue1(v interface{}) (size int)

Enqueue1 pushes a value into the queue and returns the size of the queue.

func (*Queue) Range

func (q *Queue) Range(handle func(v interface{}) bool)

Range does range all elements in queue with mutex lock, so you can't do `Enqueue` or `Dequeue` in `Range`.

func (*Queue) Size

func (q *Queue) Size() int

Size gets the count of elements in queue

type Queuer

type Queuer interface {
	Enqueue(v interface{})
	Dequeue() (v interface{}, ok bool)
	// contains filtered or unexported methods
}

Queuer interface for queue

type Stack

type Stack struct {
	sync.Mutex
	// contains filtered or unexported fields
}

Stack is a high memory efficient stack. It uses bucket to cache data and reuses the buckets.

func (*Stack) Pop

func (s *Stack) Pop() (v interface{}, ok bool)

Pop pops a value from the stack.

func (*Stack) Push

func (s *Stack) Push(v interface{})

Push pushes a value into the stack.

func (*Stack) Range

func (s *Stack) Range(handle func(v interface{}) bool)

Range does range all elements in stack with mutex lock, so you can't do `Push` or `Pop` in `Range`.

func (*Stack) Size

func (s *Stack) Size() int

Size gets the count of elements in stack

type Stacker

type Stacker interface {
	Push(v interface{})
	Pop() (v interface{}, ok bool)
	// contains filtered or unexported methods
}

Stacker interface for stack