k smallest pairs

k-smallest-pairs.bash

#!/bin/bash


ARR1=(1 2 3 4 5)
ARR2=(2 3 4 5 6)
K=5


declare -a priority_queue

enqueue() {
    local value=$1
    priority_queue+=("$value")
    heapify_up
}

enqueue_if_missing() {
    local key=$1
    local priority=$2
    local size=${#priority_queue[@]}
    for ((i=0; i<size; i++)); do
      if [[ ${priority_queue[i]%,*} == $key ]]; then
        return
      fi
    done
    enqueue $key,$priority
}

dequeue() {
    local size=${#priority_queue[@]}
    if [ $size -eq 0 ]; then
        echo "Priority queue is empty"
        return 1
    fi

    front=${priority_queue[0]%,*}
    priority_queue=("${priority_queue[@]:1}")
    heapify_down
}

heapify_up() {
    local index=$(( ${#priority_queue[@]} - 1 ))

    while [ $index -gt 0 ]; do
        local parent_index=$(( ($index - 1) / 2 ))
        parent="${priority_queue[$parent_index]##*,}"
        self="${priority_queue[$index]##*,}"
        if [ $self -lt $parent ]; then
            local temp=${priority_queue[$index]}
            priority_queue[$index]=${priority_queue[$parent_index]}
            priority_queue[$parent_index]=$temp

            index=$parent_index
        else
            break
        fi
    done
}

heapify_down() {
  local index=0
  local size=${#priority_queue[@]}

  while true; do
      local left_idx=$((2 * index + 1))
      local right_idx=$((2 * index + 2))
      local smallest_idx=$index

      local left="${priority_queue[$left_idx]##*,}"
      local smallest="${priority_queue[$smallest_idx]##*,}"
      local right="${priority_queue[$right_idx]##*,}"

      if [ "$left_idx" -lt "$size" ] && [ $left -lt $smallest ]; then
          smallest_idx=$left_idx
      fi
      if [ "$right_idx" -lt "$size" ] && [ $right -lt $smallest ]; then
          smallest_idx=$right_idx
      fi

      if [ "$smallest_idx" -ne "$index" ]; then
          local temp=${priority_queue[$index]}
          priority_queue[$index]=${priority_queue[$smallest_idx]}
          priority_queue[$smallest_idx]=$temp

          index=$smallest_idx
      else
          break
      fi
  done
}

enqueue_if_missing '0;0' $((ARR1[0]+ARR2[0]))
LEN1=${#ARR1[@]}
LEN2=${#ARR2[@]}
while [[ $K -gt 0 ]]; do
    dequeue
    current=${front#*,}
    b=${current#*;}
    c=${current%;*}
    b1=$((b+1))
    c1=$((c+1))
    [[ $b -lt $((LEN1-1)) ]] && enqueue_if_missing "$b1;$c" $((ARR1[b1]+ARR2[c]))
    [[ $c -lt $((LEN2-1)) ]] && enqueue_if_missing "$b;$c1" $((ARR1[b]+ARR2[c1]))
    ((K--))
    echo "[${ARR1[$b]}, ${ARR2[$c]}]"
done