Using Priority Queue to Compute the Slow Sums using Greedy Algor

  • 时间:2020-10-07 14:14:07
  • 分类:网络文摘
  • 阅读:97 次

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) —

推荐阅读:
6 Simple Ways to Promote Your Blog  The Secret to Writing More Compelling Blog Titles  5 Habits Of Highly Successful Bloggers  5 Ways to Connect Your Blog Content Writers  Google’s Perfect World: A New Technical SEO Framework  Boost the Visibility of Your Blog With In-Person Events  Are Top 20 Witnesses Voting Each Other? Introducing Witness-voti  How to Design a Browser History using Double-ended Queue (deque)  SteemJs: How Many Witnesses are Running on 23.1?  Illustrating the Blockchain via SteemJs – Blocks are Chain 
评论列表
添加评论