GO-递归函数中的switch语句

Question

I have an algorithm that I'm trying to implement but currently I have absolutely no clue how to do so, from a technical perspective.

We have a slice of 5 floats:

mySlice := [float1, float2, float3, float4, float5]

And a switch statement:

aFloat := mySlice[index]

switch aFloat {
  case 1:
    {
       //do something 
    }
  case 2:
    {
       //do something 
    }
  case 3:
    {
       //do something 
    }
  case 4:
    {
       //do something 
    }
  case 5:
    {
       //do something 
    }
  default:
    {
       //somehow go back to slice, take the next smallest and run
       //through the switch statement again
    }
}

What I want to do is as follows:

1. identify the smallest element of mySlice ex: smallestFloat
2. run smallestFloat through the switch statement
3. if smallestFloat gets to default case take the next smallest float from mySlice
4. do step 2 again.

I've managed to do the first step with a for loop and step 2, but I'm stuck on steps 3 and 4. I don't have an idea at the moment on how I might go about re-feeding the next smallest float from mySlice to the switch statement again...

I would appreciate any light shed on my problem.

EDIT: I figured that it would be good to put my solution to the algorithm presented above.

1. create another slice which will be a sorted version of mySlice
2. create a map[int]value where the index will correspond to the position of the value in the non-sorted slice, but the items of the map will be inserted in the same order as the sorted slice.

Result: a value sorted map with the respective indexes corresponding to the position of the original non-sorted slice

Answer 1

Here is an implementation using a Minimum Priority Queue. The original input slice of floats is not changed. It can be run on the Go playground

Note: When dealing with recursive functions, you need to be weary of stack overflows. Go does tail recursion optimizations only in limited cases. For more information on that, refer to this answer.

This particular example does even better than amortized O(log N) time, because it does not have to resize the priority queue halfway through. This makes it guaranteed O(log N).

package main

import (
    "fmt"
)

func main() {
    slice := []float64{2, 1, 13, 4, 22, 0, 5, 7, 3}
    fmt.Printf("Order before: %v
", slice)

    queue := NewMinPQ(slice)

    for !queue.Empty() {
        doSmallest(queue)
    }

    fmt.Printf("Order after: %v
", slice)
}

func doSmallest(queue *MinPQ) {
    if queue.Empty() {
        return
    }

    v := queue.Dequeue()

    switch v {
    case 1:
        fmt.Println("Do", v)
    case 2:
        fmt.Println("Do", v)
    case 3:
        fmt.Println("Do", v)
    case 4:
        fmt.Println("Do", v)
    case 5:
        fmt.Println("Do", v)
    default:
        // No hit, do it all again with the next value.
        doSmallest(queue)
    }
}

// MinPQ represents a Minimum priority queue.
// It is implemented as a binary heap.
//
// Values which are enqueued can be dequeued, but will be done
// in the order where the smallest item is returned first.
type MinPQ struct {
    values  []float64 // Original input list -- Order is never changed.
    indices []int     // List of indices into values slice.
    index   int       // Current size of indices list.
}

// NewMinPQ creates a new MinPQ heap for the given input set.
func NewMinPQ(set []float64) *MinPQ {
    m := new(MinPQ)
    m.values = set
    m.indices = make([]int, 1, len(set))

    // Initialize the priority queue.
    // Use the set's indices as values, instead of the floats
    // themselves. As these may not be re-ordered.
    for i := range set {
        m.indices = append(m.indices, i)
        m.index++
        m.swim(m.index)
    }

    return m
}

// Empty returns true if the heap is empty.
func (m *MinPQ) Empty() bool { return m.index == 0 }

// Dequeue removes the smallest item and returns it.
// Returns nil if the heap is empty.
func (m *MinPQ) Dequeue() float64 {
    if m.Empty() {
        return 0
    }

    min := m.indices[1]

    m.indices[1], m.indices[m.index] = m.indices[m.index], m.indices[1]
    m.index--
    m.sink(1)
    m.indices = m.indices[:m.index+1]
    return m.values[min]
}

// greater returns true if element x is greater than element y.
func (m *MinPQ) greater(x, y int) bool {
    return m.values[m.indices[x]] > m.values[m.indices[y]]
}

// sink reorders the tree downwards.
func (m *MinPQ) sink(k int) {
    for 2*k <= m.index {
        j := 2 * k

        if j < m.index && m.greater(j, j+1) {
            j++
        }

        if m.greater(j, k) {
            break
        }

        m.indices[k], m.indices[j] = m.indices[j], m.indices[k]
        k = j
    }
}

// swim reorders the tree upwards.
func (m *MinPQ) swim(k int) {
    for k > 1 && m.greater(k/2, k) {
        m.indices[k], m.indices[k/2] = m.indices[k/2], m.indices[k]
        k /= 2
    }
}