diff --git a/media/libmediatranscoding/include/media/AdjustableMaxPriorityQueue.h b/media/libmediatranscoding/include/media/AdjustableMaxPriorityQueue.h
new file mode 100644
index 0000000..0e8dcfd
--- /dev/null
+++ b/media/libmediatranscoding/include/media/AdjustableMaxPriorityQueue.h
@@ -0,0 +1,216 @@
+/*
+ * Copyright (C) 2020 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#ifndef ANDROID_MEDIA_ADJUSTABLE_MAX_PRIORITY_QUEUE_H
+#define ANDROID_MEDIA_ADJUSTABLE_MAX_PRIORITY_QUEUE_H
+
+#include <utils/Log.h>
+
+#include <functional>
+#include <iostream>
+#include <vector>
+
+namespace android {
+
+/*
+ * AdjustableMaxPriorityQueue is a custom max priority queue that helps managing jobs for
+ * MediaTranscodingService.
+ *
+ * AdjustableMaxPriorityQueue is a wrapper template around the STL's *_heap() functions.
+ * - Internally, it uses a std::vector<T> to store elements in a heap order.
+ * - Support adjusting item's priority while maintaining the heap property.
+ * - Support removing any item in the heap while maintaining the heap property. Note that the
+ *   removal complexity will be O(n) in worst case.
+ * - AdjustableMaxPriorityQueue needs T::operator<() at instantiation time
+ */
+template <class T, class Comparator = std::less<T>>
+class AdjustableMaxPriorityQueue {
+   public:
+    typedef typename std::vector<T>::iterator iterator;
+    typedef typename std::vector<T>::const_iterator const_iterator;
+
+    AdjustableMaxPriorityQueue();
+
+    /* Whether the queue is empty. */
+    bool empty() const;
+
+    /* Number of items in the queue. */
+    int size() const;
+
+    /* Return the top element in the queue. The queue still owns the element. */
+    const T& top() const;
+
+    /* Discards the element with highest value based on the given comparator. */
+    void pop();
+
+    /* Erases all the elements in the queue. */
+    void clear();
+
+    /*
+     * Returns the element with the highest value based on the given comparator. Queue transfer the
+     * ownership of the item to the caller. Client MUST call empty() to check whether there is
+     * element at the top before calling this.
+     */
+    T consume_top();
+
+    /* Adds an element to the heap. The queue will make a deep copy of the element. */
+    bool push(const T& item) { return pushInternal(item); }
+
+    /* Adds an element to the heap. The queue will take ownership of the element. */
+    bool push(T&& item) { return pushInternal(std::move(item)); }
+
+    /* Adds a new element to the AdjustableMaxPriorityQueue. This new element is constructed in
+     * place passing args as the arguments for its constructor. */
+    template <class... Args>
+    bool emplace(Args&&... args);
+
+    /* Remove an element from a AdjustableMaxPriorityQueue. */
+    void erase(iterator pos);
+
+    /*
+     * Rebuild a heap based on the given comparator. This MUST be called after changing the value
+     * of items.
+     */
+    void rebuild();
+
+    /*
+     * Iterators used for accessing and changing the priority.
+     * If you change the value of items through these access iterators BE SURE to call rebuild() to
+     * ensure the integrity of the heap is maintained.
+     * NOTE: The iterator pos will change after calling rebuild().
+     */
+    const iterator begin();
+    const iterator end();
+
+    /*
+     * Iterators used for accessing the priority.
+     */
+    const const_iterator begin() const;
+    const const_iterator end() const;
+
+    /* Return the backbone storage of this PriorityQueue. Mainly used for debugging. */
+    const std::vector<T>& getStorage() const { return mHeap; };
+
+   private:
+    std::vector<T> mHeap;
+
+    /* Implementation shared by both public push() methods. */
+    template <class Arg>
+    bool pushInternal(Arg&& item);
+};
+
+template <class T, class Comparator>
+AdjustableMaxPriorityQueue<T, Comparator>::AdjustableMaxPriorityQueue() {}
+
+template <class T, class Comparator>
+bool AdjustableMaxPriorityQueue<T, Comparator>::empty() const {
+    return mHeap.empty();
+}
+
+template <class T, class Comparator>
+int AdjustableMaxPriorityQueue<T, Comparator>::size() const {
+    return mHeap.size();
+}
+
+template <class T, class Comparator>
+const T& AdjustableMaxPriorityQueue<T, Comparator>::top() const {
+    DCHECK(!mHeap.empty());
+    return mHeap.front();
+}
+
+// Compares elements and potentially swaps (or moves) them until rearranged as a longer heap.
+// Complexity of this: Up to logarithmic in the distance between first and last.
+template <class T, class Comparator>
+template <class Arg>
+bool AdjustableMaxPriorityQueue<T, Comparator>::pushInternal(Arg&& item) {
+    mHeap.push_back(std::forward<Arg>(item));
+    std::push_heap(mHeap.begin(), mHeap.end(), Comparator());
+    return true;
+}
+
+template <class T, class Comparator>
+template <class... Args>
+bool AdjustableMaxPriorityQueue<T, Comparator>::emplace(Args&&... args) {
+    mHeap.emplace_back(std::forward<Args>(args)...);
+    std::push_heap(mHeap.begin(), mHeap.end(), Comparator());
+    return true;
+}
+
+// Compares elements and potentially swaps (or moves) them until rearranged as a shorter heap.
+// Complexity of this: Up to twice logarithmic in the distance between first and last.
+template <class T, class Comparator>
+void AdjustableMaxPriorityQueue<T, Comparator>::pop() {
+    DCHECK(!mHeap.empty());
+    std::pop_heap(mHeap.begin(), mHeap.end(), Comparator());
+    mHeap.pop_back();
+}
+
+// Compares elements and potentially swaps (or moves) them until rearranged as a shorter heap.
+// Complexity of this: Up to twice logarithmic in the distance between first and last.
+template <class T, class Comparator>
+T AdjustableMaxPriorityQueue<T, Comparator>::consume_top() {
+    DCHECK(!mHeap.empty());
+    std::pop_heap(mHeap.begin(), mHeap.end(), Comparator());
+    T to_return = std::move(mHeap.back());
+    mHeap.pop_back();
+    return to_return;
+}
+
+template <class T, class Comparator>
+const typename AdjustableMaxPriorityQueue<T, Comparator>::iterator
+AdjustableMaxPriorityQueue<T, Comparator>::begin() {
+    return mHeap.begin();
+}
+
+template <class T, class Comparator>
+const typename AdjustableMaxPriorityQueue<T, Comparator>::iterator
+AdjustableMaxPriorityQueue<T, Comparator>::end() {
+    return mHeap.end();
+}
+
+template <class T, class Comparator>
+const typename AdjustableMaxPriorityQueue<T, Comparator>::const_iterator
+AdjustableMaxPriorityQueue<T, Comparator>::begin() const {
+    return mHeap.begin();
+}
+
+template <class T, class Comparator>
+const typename AdjustableMaxPriorityQueue<T, Comparator>::const_iterator
+AdjustableMaxPriorityQueue<T, Comparator>::end() const {
+    return mHeap.end();
+}
+
+template <class T, class Comparator>
+void AdjustableMaxPriorityQueue<T, Comparator>::clear() {
+    mHeap.erase(mHeap.begin(), mHeap.end());
+}
+
+// Complexity of this: At most 3*std::distance(first, last) comparisons.
+template <class T, class Comparator>
+void AdjustableMaxPriorityQueue<T, Comparator>::rebuild() {
+    std::make_heap(mHeap.begin(), mHeap.end(), Comparator());
+}
+
+// Remove a random element from a AdjustableMaxPriorityQueue.
+template <class T, class Comparator>
+void AdjustableMaxPriorityQueue<T, Comparator>::erase(iterator pos) {
+    DCHECK(!mHeap.empty());
+    mHeap.erase(pos);
+    rebuild();
+}
+
+}  // namespace android
+#endif  // ANDROID_MEDIA_ADJUSTABLE_MAX_PRIORITY_QUEUE_H
\ No newline at end of file
diff --git a/media/libmediatranscoding/tests/AdjustableMaxPriorityQueue_tests.cpp b/media/libmediatranscoding/tests/AdjustableMaxPriorityQueue_tests.cpp
new file mode 100644
index 0000000..d58af4e
--- /dev/null
+++ b/media/libmediatranscoding/tests/AdjustableMaxPriorityQueue_tests.cpp
@@ -0,0 +1,289 @@
+/*
+ * Copyright (C) 2020 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+// Unit Test for AdjustableMaxPriorityQueue
+
+#define LOG_NDEBUG 0
+#define LOG_TAG "AdjustableMaxPriorityQueueTest"
+
+#include <android-base/logging.h>
+#include <android/binder_manager.h>
+#include <android/binder_process.h>
+#include <gtest/gtest.h>
+#include <media/AdjustableMaxPriorityQueue.h>
+#include <utils/Log.h>
+
+#include <algorithm>
+#include <functional>
+#include <iterator>
+#include <list>
+#include <queue>
+#include <unordered_map>
+
+namespace android {
+
+class IntUniquePtrComp {
+   public:
+    bool operator()(const std::unique_ptr<int>& lhs, const std::unique_ptr<int>& rhs) const {
+        return *lhs < *rhs;
+    }
+};
+
+// Test the heap property and make sure it is the same as std::priority_queue.
+TEST(AdjustableMaxPriorityQueueTest, BasicAPIS) {
+    AdjustableMaxPriorityQueue<std::pair<float, char*>> heap;
+    std::priority_queue<std::pair<float, char*>> pq;
+    AdjustableMaxPriorityQueue<std::pair<float, char*>> remove_queue;
+
+    // Push a set of values onto both AdjustableMaxPriorityQueue and priority_queue
+    // Also compute the sum of those values
+    double sum = 0;
+    for (int i = 0; i < 10; ++i) {
+        float value = 2.1 * i;
+        sum += value;
+        heap.push(std::pair<float, char*>(value, nullptr));
+        pq.push(std::pair<float, char*>(value, nullptr));
+        remove_queue.push(std::pair<float, char*>(value, nullptr));
+    }
+
+    // Test the iterator by using it to subtract all values from earlier sum
+    AdjustableMaxPriorityQueue<std::pair<float, char*>>::iterator it;
+    for (it = heap.begin(); it != heap.end(); ++it) {
+        sum -= it->first;
+    }
+    EXPECT_EQ(0, sum);
+
+    // Test the size();
+    EXPECT_EQ(10, heap.size());
+
+    // Testing pop() by popping values from both queues and compare if they are the same.
+    // Also check each pop is smaller than the previous pop max value.
+    float max = 1000;
+    while (!heap.empty()) {
+        float value = heap.top().first;
+        ALOGD("Value is %f ", value);
+        EXPECT_EQ(value, pq.top().first);
+        EXPECT_LE(value, max);
+        max = value;
+        heap.pop();
+        pq.pop();
+    }
+
+    // Test erase() by removing values and ensuring the heap
+    // condition is still met as miscellaneous elements are
+    // removed from the heap.
+    int iteration_mixer = 0;
+    float previous_value = remove_queue.top().first;
+
+    while (!remove_queue.empty()) {
+        int iteration_count = iteration_mixer % remove_queue.size();
+
+        AdjustableMaxPriorityQueue<std::pair<float, char*>>::iterator iterator =
+                remove_queue.begin();
+
+        // Empty loop as we just want to advance the iterator.
+        for (int i = 0; i < iteration_count; ++i, ++iterator) {
+        }
+
+        remove_queue.erase(iterator);
+        float value = remove_queue.top().first;
+        remove_queue.pop();
+
+        EXPECT_GE(previous_value, value);
+
+        ++iteration_mixer;
+        previous_value = value;
+    }
+}
+
+TEST(AdjustableMaxPriorityQueueTest, BasicWithMoveOnly) {
+    AdjustableMaxPriorityQueue<std::unique_ptr<int>, IntUniquePtrComp> heap;
+
+    auto smaller = std::make_unique<int>(1);
+    EXPECT_TRUE(heap.push(std::move(smaller)));
+    EXPECT_EQ(1, *heap.top());
+    EXPECT_EQ(1, heap.size());
+
+    auto bigger = std::make_unique<int>(2);
+    heap.push(std::move(bigger));
+    EXPECT_EQ(2, *heap.top());
+
+    auto biggest = std::make_unique<int>(3);
+    EXPECT_TRUE(heap.push(std::move(biggest)));
+
+    EXPECT_EQ(3, heap.size());
+    // Biggest should be on top.
+    EXPECT_EQ(3, *heap.top());
+
+    biggest = heap.consume_top();
+    EXPECT_EQ(3, *biggest);
+
+    bigger = heap.consume_top();
+    EXPECT_EQ(2, *bigger);
+
+    smaller = heap.consume_top();
+    EXPECT_EQ(1, *smaller);
+
+    EXPECT_TRUE(heap.empty());
+}
+
+TEST(AdjustableMaxPriorityQueueTest, TestChangingItem) {
+    AdjustableMaxPriorityQueue<std::unique_ptr<int>, IntUniquePtrComp> heap;
+    using HeapIterator =
+            AdjustableMaxPriorityQueue<std::unique_ptr<int>, IntUniquePtrComp>::iterator;
+
+    int testValues[] = {1, 2, 3};
+    // Map to save each value's position in the heap.
+    std::unordered_map<int, HeapIterator> itemToIterratorMap;
+
+    // Insert the test values into the heap.
+    for (auto value : testValues) {
+        auto item = std::make_unique<int>(value);
+        EXPECT_TRUE(heap.push(std::move(item)));
+    }
+
+    // Save each value and its pos in the heap into the map.
+    for (HeapIterator iter = heap.begin(); iter != heap.end(); iter++) {
+        itemToIterratorMap[*iter->get()] = iter;
+    }
+
+    // Change the item with value 1 -> 4. And expects the 4 to be the top of the HEAP after that.
+    // After changing, the heap should contain [2,3,4].
+    auto newValue = std::make_unique<int>(4);
+    itemToIterratorMap[1]->swap(newValue);
+    heap.rebuild();
+    EXPECT_EQ(4, *heap.top());
+
+    // Change the item with value 2 -> 5. And expects the 5 to be the top of the HEAP after that.
+    auto newValue2 = std::make_unique<int>(5);
+    itemToIterratorMap[2]->swap(newValue2);
+    heap.rebuild();
+    EXPECT_EQ(5, *heap.top());
+}
+
+TEST(AdjustableMaxPriorityQueueTest, TestErasingItem) {
+    AdjustableMaxPriorityQueue<std::unique_ptr<int>, IntUniquePtrComp> heap;
+    using HeapIterator =
+            AdjustableMaxPriorityQueue<std::unique_ptr<int>, IntUniquePtrComp>::iterator;
+
+    int testValues[] = {1, 2, 3};
+    // Map to save each value's position in the heap.
+    std::unordered_map<int, HeapIterator> itemToIterratorMap;
+
+    // Insert the test values into the heap.
+    for (auto value : testValues) {
+        auto item = std::make_unique<int>(value);
+        EXPECT_TRUE(heap.push(std::move(item)));
+    }
+
+    // Save each value and its pos in the heap into the map.
+    for (HeapIterator iter = heap.begin(); iter != heap.end(); iter++) {
+        itemToIterratorMap[*iter->get()] = iter;
+    }
+
+    // The top of the heap must be 3.
+    EXPECT_EQ(3, *heap.top());
+
+    // Remove 3 and the top of the heap should be 2.
+    heap.erase(itemToIterratorMap[3]);
+    EXPECT_EQ(2, *heap.top());
+
+    // Reset the iter pos in the heap.
+    itemToIterratorMap.clear();
+    for (HeapIterator iter = heap.begin(); iter != heap.end(); iter++) {
+        itemToIterratorMap[*iter->get()] = iter;
+    }
+
+    // Remove 2 and the top of the heap should be 1.
+    heap.erase(itemToIterratorMap[2]);
+    EXPECT_EQ(1, *heap.top());
+
+    // Reset the iter pos in the heap as iterator pos changed after
+    itemToIterratorMap.clear();
+    for (HeapIterator iter = heap.begin(); iter != heap.end(); iter++) {
+        itemToIterratorMap[*iter->get()] = iter;
+    }
+
+    // Remove 1 and the heap should be empty.
+    heap.erase(itemToIterratorMap[1]);
+    EXPECT_TRUE(heap.empty());
+}
+
+// Test the heap property and make sure it is the same as std::priority_queue.
+TEST(AdjustableMaxPriorityQueueTest, TranscodingJobTest) {
+    // Test data structure that mimics the Transcoding job.
+    struct TranscodingJob {
+        int32_t priority;
+        int64_t createTimeUs;
+    };
+
+    // The job is arranging according to priority with highest priority comes first.
+    // For the job with the same priority, the job with early createTime will come first.
+    class TranscodingJobComp {
+       public:
+        bool operator()(const std::unique_ptr<TranscodingJob>& lhs,
+                        const std::unique_ptr<TranscodingJob>& rhs) const {
+            if (lhs->priority != rhs->priority) {
+                return lhs->priority < rhs->priority;
+            }
+            return lhs->createTimeUs > rhs->createTimeUs;
+        }
+    };
+
+    // Map to save each value's position in the heap.
+    std::unordered_map<int, TranscodingJob*> jobIdToJobMap;
+
+    TranscodingJob testJobs[] = {
+            {1 /*priority*/, 66 /*createTimeUs*/},  // First job,
+            {2 /*priority*/, 67 /*createTimeUs*/},  // Second job,
+            {2 /*priority*/, 66 /*createTimeUs*/},  // Third job,
+            {3 /*priority*/, 68 /*createTimeUs*/},  // Fourth job.
+    };
+
+    AdjustableMaxPriorityQueue<std::unique_ptr<TranscodingJob>, TranscodingJobComp> jobQueue;
+
+    // Pushes all the jobs into the heap.
+    for (int jobId = 0; jobId < 4; ++jobId) {
+        auto newJob = std::make_unique<TranscodingJob>(testJobs[jobId]);
+        jobIdToJobMap[jobId] = newJob.get();
+        EXPECT_TRUE(jobQueue.push(std::move(newJob)));
+    }
+
+    // Check the job queue size.
+    EXPECT_EQ(4, jobQueue.size());
+
+    // Check the top and it should be Forth job: (3, 68)
+    const std::unique_ptr<TranscodingJob>& topJob = jobQueue.top();
+    EXPECT_EQ(3, topJob->priority);
+    EXPECT_EQ(68, topJob->createTimeUs);
+
+    // Consume the top.
+    std::unique_ptr<TranscodingJob> consumeJob = jobQueue.consume_top();
+
+    // Check the top and it should be Third Job (2, 66)
+    const std::unique_ptr<TranscodingJob>& topJob2 = jobQueue.top();
+    EXPECT_EQ(2, topJob2->priority);
+    EXPECT_EQ(66, topJob2->createTimeUs);
+
+    // Change the Second job's priority to 4 from (2, 67) -> (4, 67). It should becomes top of the
+    // queue.
+    jobIdToJobMap[1]->priority = 4;
+    jobQueue.rebuild();
+    const std::unique_ptr<TranscodingJob>& topJob3 = jobQueue.top();
+    EXPECT_EQ(4, topJob3->priority);
+    EXPECT_EQ(67, topJob3->createTimeUs);
+}
+}  // namespace android
\ No newline at end of file
diff --git a/media/libmediatranscoding/tests/Android.bp b/media/libmediatranscoding/tests/Android.bp
index f3cc4c5..8191b00 100644
--- a/media/libmediatranscoding/tests/Android.bp
+++ b/media/libmediatranscoding/tests/Android.bp
@@ -35,4 +35,14 @@
     defaults: ["libmediatranscoding_test_defaults"],
 
     srcs: ["TranscodingClientManager_tests.cpp"],
+}
+
+//
+// AdjustableMaxPriorityQueue unit test
+//
+cc_test {
+    name: "AdjustableMaxPriorityQueue_tests",
+    defaults: ["libmediatranscoding_test_defaults"],
+
+    srcs: ["AdjustableMaxPriorityQueue_tests.cpp"],
 }
\ No newline at end of file
diff --git a/media/libmediatranscoding/tests/build_and_run_all_unit_tests.sh b/media/libmediatranscoding/tests/build_and_run_all_unit_tests.sh
index 9832696..d8e4830 100644
--- a/media/libmediatranscoding/tests/build_and_run_all_unit_tests.sh
+++ b/media/libmediatranscoding/tests/build_and_run_all_unit_tests.sh
@@ -21,3 +21,6 @@
 
 echo "testing TranscodingClientManager"
 adb shell /data/nativetest64/TranscodingClientManager_tests/TranscodingClientManager_tests
+
+echo "testing AdjustableMaxPriorityQueue"
+adb shell /data/nativetest64/AdjustableMaxPriorityQueue_tests/AdjustableMaxPriorityQueue_tests