Using Priority Queue to Compute the Slow Sums using Greedy Algorithm

Slow Sums Algorithms

Suppose we have a list of N numbers, and repeat the following operation until we’re left with only a single number: Choose any two numbers and replace them with their sum. Moreover, we associate a penalty with each operation equal to the value of the new number, and call the penalty for the entire list as the sum of the penalties of each operation.

For example, given the list [1, 2, 3, 4, 5], we could choose 2 and 3 for the first operation, which would transform the list into [1, 5, 4, 5] and incur a penalty of 5. The goal in this problem is to find the worst possible penalty for a given input.

1	int getTotalTime(int[] arr)

int getTotalTime(int[] arr)

Input:
An array arr containing N integers, denoting the numbers in the list.
Output format:
An int representing the worst possible total penalty.

Constraints:
1 ≤ N ≤ 10^6
1 ≤ Ai ≤ 10^7, where *Ai denotes the ith initial element of an array.
The sum of values of N over all test cases will not exceed 5 * 10^6.

Example
arr = [4, 2, 1, 3]
output = 26

First, add 4 + 3 for a penalty of 7. Now the array is [7, 2, 1]
Add 7 + 2 for a penalty of 9. Now the array is [9, 1]
Add 9 + 1 for a penalty of 10. The penalties sum to 26.

Greedy Algorithm to Compute the Slowest Sum of Array using Priority Queue

The greedy algorithm works in this problem. Every time, we need to add the top 2 largest numbers and accumulate the penality. We can construct a priority queue from the given array, then simulate the process until we have only 1 element in the queue. The answer (Slow Sum) will be accumulated.

The intermediate sum will need to be added back to the priority queue. The complexity is O(NlogN) – where N is the number of the elements in the array. Inserting a new element into a existing priority queue takes O(logN) time to rebuild the priority queue. And there are N numbers, so the overall complexity is O(NLogN).

1
2
3
4
5
6
7
8
9
10
11
12
13

int computeSlowSum(vector<int> &arr) {
  priority_queue<int> data(begin(arr), end(arr));
  int ans = 0;
  while (data.size() > 1) {
    auto a = data.top();
    data.pop();
    auto b = data.top();
    data.pop();
    ans += a + b;
    data.push(a + b);
  }
  return ans;
}

int computeSlowSum(vector<int> &arr) {
  priority_queue<int> data(begin(arr), end(arr));
  int ans = 0;
  while (data.size() > 1) {
    auto a = data.top();
    data.pop();
    auto b = data.top();
    data.pop();
    ans += a + b;
    data.push(a + b);
  }
  return ans;
}

We can sort the array in O(NLogN) complexity and do a partial sort (inserting a new element into a sorted array) in O(logN). In the following Python code, we use the bisect.insort() to add a new element into the sorted array at its correct position. The overall complexity is O(NLogN) as well.

1
2
3
4
5
6
7
8

def computeSlowSum(arr):
  ans = 0
  arr.sort()
  while len(arr) > 1:
    v = arr.pop() + arr.pop()
    ans += v
    bisect.insort(arr, v)
  return ans

def computeSlowSum(arr):
  ans = 0
  arr.sort()
  while len(arr) > 1:
    v = arr.pop() + arr.pop()
    ans += v
    bisect.insort(arr, v)
  return ans

–EOF (The Ultimate Computing & Technology Blog) —